Aufwand O-Kalkül < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hi!
Ich versuche grad das Zeug mit den Komplexitätsklassen und den landausymbolen zu verstehen.
Und zwar bin ich gerade bei dem O-Kalkül und würde nun gerne die kleinste obere Schranke Berechnen. Bei normalen Zahlen klappt es auch schon ganz gut. Nun muss man aber ja auch oft den Aufwand von einer Funktion berechnen.
Hier mal ein Beispiel:
for (int i=1; i<=n; ++i){
for (int j=1; j<=n; j*=2){
if (j % 2 == 1){
f(i) // O(i)
}else{
g(); // O(1)
}
}
}
Wie gehe ich denn bei sowas vor?
Konstanten fallen ja einfach weg, aber hier hab ich ja keine richtigen Potenzen usw.
Wäre lieb, wenn mir jemand erklären könnte wie man bei so nem Code vorgeht um die Schrnake zu berechnen.
Danke
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:36 Mi 08.06.2011 | | Autor: | felixf |
Moin!
> Ich versuche grad das Zeug mit den Komplexitätsklassen und
> den landausymbolen zu verstehen.
>
> Und zwar bin ich gerade bei dem O-Kalkül und würde nun
> gerne die kleinste obere Schranke Berechnen. Bei normalen
> Zahlen klappt es auch schon ganz gut. Nun muss man aber ja
> auch oft den Aufwand von einer Funktion berechnen.
>
> Hier mal ein Beispiel:
>
> for (int i=1; i<=n; ++i){
> for (int j=1; j<=n; j*=2){
> if (j % 2 == 1){
> f(i) // O(i)
> }else{
> g(); // O(1)
> }
> }
> }
>
> Wie gehe ich denn bei sowas vor?
Von innen nach aussen.
Den innersten Schritt hast du ja schon: die asymptotischen Laufzeiten von $f(i)$ und $g()$. Jetzt willst du damit die Laufzeit der inneren Schleife
| 1: |
| | 2: | for (int j=1; j<=n; j*=2){
| | 3: | if (j % 2 == 1){
| | 4: | f(i) // O(i)
| | 5: | }else{
| | 6: | g(); // O(1)
| | 7: | }
| | 8: | }
|
bestimmen. Dazu beachte erst, welche Werte $j$ annimmt. Es nimmt die Werte $1, 2, 4, 8, 16, [mm] \dots, 2^k$ [/mm] an, mit $k$ maximal mit [mm] $2^k \le [/mm] n$.
Diese Zahlen sind modulo 2 alle 0, ausser 1. D.h. $f(i)$ wird genau einmal durchlaufen (falls $j = 1$ ist), und danach wird $g()$ genau $k - 1$ mal aufgerufen.
Aus [mm] $2^k \approx [/mm] n$ folgt [mm] $\log_2 [/mm] n [mm] \approx [/mm] k$, womit $k = [mm] O(\log [/mm] n)$ ist. Die Gesamtlaufzeit der inneren Schleife ist also $O(i) + [mm] O(\log [/mm] n) [mm] \cdot [/mm] O(1) = O(i + [mm] \log [/mm] n)$.
Jetzt zur aeusseren Schleife. Die wird von $i = 1$ bis $n$ durchlaufen, fuer jeden ganzzahligen Wert $i$ dazwischen einmal. Die asymptotische Laufzeit ist also [mm] $\sum_{i=1}^n [/mm] O(i + [mm] \log [/mm] n) = [mm] O(\sum_{i=1}^n [/mm] i + [mm] \sum_{i=1}^n \log [/mm] n)$. Jetzt ist [mm] $\sum_{i=1}^n [/mm] i = [mm] \frac{n (n + 1)}{2} [/mm] = [mm] O(n^2)$ [/mm] und [mm] $\sum_{i=1}^n \log [/mm] n = n [mm] \log [/mm] n$, womit dies ganze gleich [mm] $O(n^2 [/mm] + n [mm] \log [/mm] n) = [mm] O(\max(n^2, [/mm] n [mm] \log [/mm] n))$ ist. Da [mm] $n^2 \ge [/mm] n [mm] \log [/mm] n$ ist, ist es also gleich [mm] $O(n^2)$.
[/mm]
Damit ist die Gesamtlaufzeit [mm] $O(n^2)$.
[/mm]
So. Jetzt versuch mal das nachzuvollziehen 
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:32 Sa 11.06.2011 | | Autor: | BlackSalad |
Wow Danke!
Ich glaube ich habs jetzt verstanden wie das geht.
Man muss also die schleifen einzeln betrachten.
Wenn ich versuch das jetzt mal bisschen zu üben, wenn ich noch ne Frage dazu habe, meld ich mich nochmal.
DankeschöN!
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 14:28 Sa 11.06.2011 | | Autor: | BlackSalad |
Hätt nochmal ne Frage. Hab jetzt ein paar durchgespielt, bin mir aber bei der da nicht so sicher:
1: for (int i=1; i<=n; ++i){
2: for (int j=1; j<=i; ++j){
3: if (j % 2 == 1){
4: h(i, j); // O(j)
5: }else{
6: g(); // O(1)
7: }
8: }
9: }
Also muss ich ja jetzt erst mal nach der inneren schleife schauen:
j nimmt die werte von 1 bis i-1 an.
Also 1, 2, 3, 4, 5 usw.
also j=j+1.
also ist j % 2 == 1 nur im fall von j=2 true.
Also wird h(j) nur einmal ausgeführt pro aufruf der inneren schleife.
und g() wird k-1 mal ausgeführt und kann vernachlässigt werden, da da immer ein linearer Aufwand vorliegt und der Aufwand O(j) somit schon größer ist.
Nun also zur äßeren Schleife:
for (int i=1; i<=n; ++i)
diese wird (n-1) mal ausgeführt.
und bei jeder ausführung wird auch die innere schleife ausgeführt.
Nur wie mache ich jetzt weiter?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:39 So 12.06.2011 | | Autor: | BlackSalad |
hat sich erledigt.
|
|
|
|
