/***********************************************************************
 *  Mönsterigenkänning readme.txt                                      *
 ***********************************************************************/

/***********************************************************************
 *  Empirisk    Fyll i tabellen nedan med riktiga körtider i sekunder  *
 *  analys      när det känns vettigt att vänta på hela beräkningen.   *
 *              Ge uppskattningar av körtiden i övriga fall.           *
 *                                                                     *
 ***********************************************************************/

      N       brute       sortering
 ----------------------------------
    150       0.007          <0.000
    200       0.015          <0.000
    300       0.038           0.004
    400       0.072           0.004
    800       0.475           0.017
   1600       3.680           0.076
   3200      29.776           0.317
   6400     250.432           1.357
  12800    2000.???           5.822


/*************************************************************************
 *  Teoretisk   Ge ordo-uttryck för värstafallstiden för programmen som  *
 *  analys      en funktion av N. Ge en kort motivering.                 *
 *                                                                       *
 *************************************************************************/

** Brute

for (int i = 0 ; i < N-3 ; ++i) {                            <-- N
  for (int j = i+1 ; j < N-2 ; ++j) {                          <-- N
    for (int k = j+1 ; k < N-1 ; ++k) {                          <-- N
      if (points.at(i).slopeTo(points.at(j)) ...
        for (int m{k+1} ; m < N ; ++m) {                           <-- N
          if (points.at(i).slopeTo(points.at(j)) ...
            render_line(scene, points.at(i), points.at(m));
            a.processEvents(); // show rendered line
          }
        }
      }
    }
  }
}

slopeTo är O(1) (endast branching och vanlig aritmetik) så algoritmen är worst
case O(N^4).

** Sortering

  for (int p1 = 0; p1 < N-1; p1++) {                             <-- N
    angles.clear();
    for (int p2 = p1 + 1; p2 < N; p2++) {                          <-- N
      double angle = points.at(p1).slopeTo(points.at(p2));
      angles.push_back({ angle, points.at(p2) });
    }
    sort(angles.begin(), angles.end());                            <-- N log N

    double prev_angle = angles[0].first;
    int num_in_row = 0;
    for (int i = 1; i < angles.size(); i++) {                      <-- N
      if (angles[i].first == prev_angle) {
        num_in_row++;
        if (num_in_row >= 2) {
          render_line(scene, points.at(p1), angles[i].second);
        }
      } else {
        num_in_row = 0;
      }
      prev_angle = angles[i].first;
    }
    if (num_in_row >= 2) {
        render_line(scene, points.at(p1), angles[angles.size() - 1].second);
    }
  }

Algoritmen kommer i värsta fall för varje punkt (O(N)) sortera efter lutningen
mot varje annan punkt (O(N log N)) => tidskomplexitet worst case O(N^2 log N).