Wie kann man wissen, wenn Big O logarithmisch ist?

Question

Meine Frage ergibt sich aus dem Beitrag "Plain English Erklärung der Big O" . Ich weiß nicht, die genaue Bedeutung für logarithmische Komplexität. Ich weiß, dass ich eine Regression zwischen der Zeit und der Anzahl der Operationen machen und dem X-Quadrat-Wert berechnen und bestimmen so die Komplexität. Allerdings mag ich eine Methode wissen, dass es auf dem Papier schnell zu bestimmen.

Wie bestimmen Sie logarithmische Komplexität? Gibt es einige gute Benchmarks?

Answer 1

Nicht sicher, ob dies ist, was Sie meinen, aber ... logarithmische Komplexität entsteht in der Regel, wenn Sie mit einer Spread-out-Datenstruktur wie ein ausgewogenen binären Baum arbeiten, die 1 Knoten an der Wurzel enthält, 2 Kinder, 4 Enkel, 8 Urenkel usw. im Grunde genommen auf jeder Ebene die Anzahl der Knoten werden von einem Faktor (2) multipliziert wird, aber immer noch nur eine davon ist in der Iteration beteiligt. Oder als ein anderes Beispiel, bei dem eine Schleife der Index in jedem Schritt verdoppelt:

for (int i = 1; i < N; i *= 2) { ... }

Solche Dinge sind die Unterschriften von logarithmischer Komplexität.

Answer 2

Nicht streng, aber es hat Sie einen Algorithmus, der im Wesentlichen der Arbeit spaltet erforderlich, um bei jeder Iteration um die Hälfte getan wird, dann haben Sie logarithmische Komplexität. Das klassische Beispiel ist binäre Suche.

Answer 3

Master-Theorem in der Regel funktioniert.

Answer 4

Wenn Sie nur wollen, über logarithmisch Big Oh wissen, auf der Suche nach, wenn Sie Ihre Daten in der Hälfte jeden Schritt des erneuten Auftretens geschnitten werden.

Das ist, weil, wenn Sie Daten verarbeiten, die vor ihm 1/2 so groß wie der Schritt ist, es eine unendliche Reihe ist.

Answer 5

Hier ist eine andere Art und Weise, es zu sagen.

Angenommen, Ihr Algorithmus linear in der Anzahl der Stellen in der Größe des Problems ist. Also, vielleicht haben Sie einen neuen Algorithmus eine große Anzahl Faktor, dass Sie nachweisen können, in der Anzahl der Ziffern linear. Eine 20-stellige Zahl nimmt damit doppelt so lang wie eine 10-stellige Nummer Faktor Ihren Algorithmus. Dies würde log Komplexität haben. (Und es wäre für den Erfinder etwas wert sein.)

Bisection hat das gleiche Verhalten. Es dauert etwa 10 bisection Schritte, um die Intervall-Länge um einen Faktor von 1024 = 2 ^ 10, zu schneiden, sondern nur 20 Stufen werden das Intervall um einen Faktor von 2 ^ 20 schneiden.

Komplexität Log bedeutet nicht immer ein Algorithmus auf alle Probleme schnell. Der lineare Faktor vor dem O (log (n)) kann groß sein. Also Ihr Algorithmus auf kleine Probleme schrecklich sein kann, nicht sinnvoll werden, bis das Problem Größe merklich groß ist, dass andere Algorithmen sterben exponentiell (oder Polynom) Tod.