blob: f411b3fba29dcce50bf2074768614f753da22565 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
/***********************************************************************
* 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).
|
