Komplexität für verschachtelte Schleifen, die durch 2 teilen

Question

Komplexität für verschachtelte Schleifen, die durch 2 teilen

8

Ich versuche, die Komplexität einer for-Schleife mit Hilfe der Big-O-Notation herauszufinden. Ich habe das schon früher in meinen anderen Klassen gemacht, aber dieses ist strenger als die anderen, weil es sich um den eigentlichen Algorithmus handelt. Der Code ist wie folgt:

%Vor%

Ich bin angekommen, dass die erste Schleife von O ist (log_2 (n)). Was die zweite Runde angeht, bin ich etwas verloren! Danke für die Hilfe bei der Analyse.

c loops big-o

Hassan Bendouj 25.05.2013, 10:06

quelle

3 Antworten

Tags und Links c loops big-o

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Warum ist diese Codezeile beim Klicken auf eine Schaltfläche mit JavaScript erforderlich?

score 4 · Answer 1

4

Um die Zeitkomplexität Ihres Algorithmus formal zu lösen, können Sie die folgenden Schritte mit der Sigma-Notation verwenden:

Sehen Sie sich auch die letzte Folie dieses sehr interessanten Dokuments an Dr. Jauhar.

Mohamed Ennahdi El Idrissi 18.03.2014 01:07

quelle

score 2 · Answer 2

2

Die Gesamtanzahl der Iterationen der inneren Schleife ist n + n / 2 + n / 4 + ... + 1, was ungefähr 2n ist. Also ist die Komplexität O (n).

Inspired 25.05.2013 10:09

quelle

score 1 · Answer 3

1

Die Komplexität sollte O(n) sein. Es bildet eine geometrische Reihe (nicht genau aber ungefähr).

Die Schleife läuft für n+ n/2 + n/4 + .... +1 , was ca. 2n ist.

Und O(2n) = O(n) .

dejavu 25.05.2013 10:57

quelle