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

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Asymptotische Laufzeit bestimmen » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Asymptotische Laufzeit bestimmen
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
Rambo95
Grünschnabel


Dabei seit: 22.11.2018
Beiträge: 1

Asymptotische Laufzeit bestimmen Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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?

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Rambo95: 24.11.2018 18:07.

22.11.2018 13:58 Rambo95 ist offline E-Mail an Rambo95 senden Beiträge von Rambo95 suchen Nehmen Sie Rambo95 in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Asymptotische Laufzeit bestimmen