Laufzeitabschätzungen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Fall 1: wenn c < [mm] log_{b}a [/mm] dann T(n) = [mm] (n^{log_{b}a})
[/mm]
Fall 2: wenn c = [mm] log_{b}a [/mm] dann T(n) = [mm] (n^{c} [/mm] log n)
Fall 3: wenn c > [mm] log_{b}a [/mm] dann T(n) = [mm] (n^{c})
[/mm]
1)
Wenn ich die Funktion habe:
void not_so_strange(int n, int digit) {
strange(n, digit);
for (int i=0; i<7; ++i) not_so_strange(n/digit, digit);
strange(n, digit);
}
Und strange(n, digit); ergibt O(n^digit) und sie 2x mal aufgeführt wird, mein digit == 6
dann ergibt das für c=12;
a regelt das die Funktion konstant 7 mal aufgeführt wird also: a=7;
wegen n/6, b = 6
erfüllt also alles notwendige für das Master Theorem
12>log6 von 7:
also O(n^12)
2)
void doing(int n, int digit) {
if (n==0) return;
done(n);
for (int i=0; i<digit; ++i)
doing(n/2, digit);
done(n);
doing(n/2, digit)
}
[mm] done(n)==O(n^4) [/mm]
Also hier müsste man auch das Theorem anwenden könnten, digit ist konstant, n wird durch eine fixe größe definiert
c = 8 –> 2 * [mm] (n^4) [/mm]
a = digit+1 = 6 + 1 –> Plus eins, weil die rekursive Funktion nochmal ausgeführt wird später
b = 2
8 > log2 7 = (2,8)
Also wieder [mm] O(n^8) [/mm]
3)
void done(int n) {
for (int i=1; i<n; i=i*3)
for (int j=2*n; j>0; j=j/2) –> Das mal 2 kann ich ignorieren, da es nur einmal passiert oder?
cout<<"easy";
}
O(log [mm] n)^2 [/mm]
4)
void todo(int n) {
if (n==0) return;
for (int i=0; i<2*n; ++i);
todo(n-1);
}
T(n) = T(n-1)*n = T(n-2)*n*n = [mm] O(n^2) [/mm]
5)
void doing(int n, int digit) {
if (n==0) return;
for (int i=0; i<n/2; ++i) todo(n);
for (int j=3; j>0; –j) doing(n/digit, digit);
}
c = [mm] n^3 [/mm] = 3
a = 3
b = digit = 6
3 > log6 3 = 0,6
[mm] O(n^3) [/mm]
Stimmt das? Eine Kontrolle wäre super :)
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:20 Do 30.06.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
