Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Suche » Suchergebnis » Hallo Gast [Anmelden|Registrieren]
Zeige Beiträge 1 bis 1 von 1 Treffern
Autor Beitrag
Thema: Asymptotische Laufzeit bestimmen
Rambo95

Antworten: 0
Hits: 2.781
Asymptotische Laufzeit bestimmen 22.11.2018 13:58 Forum: Algorithmen


Meine Frage:
Hallo, ich habe folgenden Pseudocode:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
digit = 1 

for ( i=0 to n ) 
   for ( j=i to n ) 
      count = n 

      while ( count > 0 ) 
      digit = digit +1 
      count = count / 2 
 
return digit


Die asymptotische Laufzeit ist gesucht.

Meine Ideen:
Für die ersten beiden for-Schleifen ist die Laufzeit O(n)=n, da in der zweiten Schleife j=i.

Aber bei der while-Schleife denke ich, dass es O(n)=log(n) ist, da count immer halbiert wird.

Somit O(n)=n^2 * log(n) ?

Liege ich damit richtig?
Zeige Beiträge 1 bis 1 von 1 Treffern