diff options
Diffstat (limited to 'labb7')
| -rw-r--r-- | labb7/res/readme.txt | 79 |
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). |