update readme

1 files changed, 79 insertions, 0 deletions

diff --git a/labb7/res/readme.txt b/labb7/res/readme.txt
new file mode 100644
index 0000000..55a3049
--- /dev/null
+++ b/labb7/res/readme.txt
@@ -0,0 +1,79 @@
+/***********************************************************************
+ *  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 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 (N) sortera lutningen mot varje
+annan punkt (N log N) med en tidskomplexitet O(N^2 log N).