Wie zu wissen, wenn Big O Logarithmisch ist?

Meine Frage ergibt sich aus der Post "Plain English Explanation of Big O". Ich kenne die genaue Bedeutung der logarithmischen Komplexität nicht. Ich weiß, dass ich zwischen dem Zeitpunkt und der Anzahl der Operationen eine Regression vornehmen und den X-Quadrat-Wert berechnen kann, und bestimme so die Komplexität. Ich möchte jedoch eine Methode kennen, um es schnell auf Papier zu bestimmen.Wie zu wissen, wenn Big O Logarithmisch ist?

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

Quelle

2009-04-15 Léo Léopold Hertz 준영

Nicht sicher, ob Sie das meinen, aber ... logarithmische Komplexität entsteht normalerweise, wenn Sie mit einer verteilten Datenstruktur wie einem ausgewogenen Binärbaum arbeiten, der 1 Knoten an der Wurzel, 2 Kinder, 4 Enkelkinder, 8 Urenkel usw. Grundsätzlich wird auf jeder Ebene die Anzahl der Knoten mit einem Faktor (2) multipliziert, aber immer noch ist nur einer von ihnen an der Iteration beteiligt. Oder als ein anderes Beispiel, bei dem eine Schleife der Index verdoppelt sich bei jedem Schritt:

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

Solche Dinge sind die Unterschriften der logarithmische Komplexität.

Quelle

2009-04-15 00:28:06

+1 sehr interessant. Ich suche eher nach deinen Beispielen mehr. Ist der Algorithmus logarithmisch wie folgt: for (int i = BIG_number; i> N; i * = 1/2) {...} –

1/2 ist Null in ganzzahliger Division, aber wenn Sie stattdessen "i/= 2" verwenden , Ja, so ist es. (Wenn das der spezielle Algorithmus ist, über den Sie sich wundern, könnte es eine gute Idee gewesen sein, ihn in Ihre Frage aufzunehmen.) –

Master theorem funktioniert normalerweise.

Quelle

2009-04-15 00:15:12

Etwas schwierig zu denken, aber sehr gut, wenn Sie es beherrschen. – samoz

Nicht streng, aber Sie haben einen Algorithmus, der im Wesentlichen die Arbeit teilt, die bei jeder Iteration halbiert werden muss, dann haben Sie logarithmische Komplexität. Das klassische Beispiel ist die binäre Suche.

Quelle

2009-04-15 00:18:56

nicht unbedingt. Ich verstehe, was Sie zu implizieren versuchen, aber nur weil Sie die Arbeit in zwei Hälften teilen bedeutet das nicht, dass Sie eine logarithmische Komplexität bekommen, Sie könnten sogar exponentielle Zeit dafür haben. Sie müssen beachten, wie die Lösungen auch neu kombiniert werden und wie die geteilten Probleme gelöst werden. Es gibt viele Fälle, in denen der Rekombinationsschritt dominiert. Siehe Master Theorem oder besser lösen Sie die Wiederholung ohne das Theorem. Unter einer einfachen Wiederholung gibt es viele Überraschungen. – unj2

@unjaan: Ich glaube, du verstehst mich falsch. Ich habe nicht nur gesagt, die Arbeit in zwei Teile zu teilen, ich sagte "die Arbeit musste bei jeder Iteration halbiert werden". Was ich meine ist, wenn bei jedem Schritt die Hälfte der Arbeit im Vergleich zum vorherigen Schritt zu tun ist, dann haben Sie logarithmische Komplexität (für die Arbeit, lesen Berechnungen). –

Wenn Sie nur über logarithmische Big Oh wissen wollen, achten Sie darauf, wenn Ihre Daten in jedem Schritt der Wiederholung halbiert werden.

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

Quelle

2009-04-15 00:19:02 samoz

Nicht unbedingt 1/2.1/c funktioniert, solange "c" konstant ist. –

aber 1/2 ist mehr "intuitiv" –

Nun, normalerweise, wenn man über Big O spricht, bedeutet log Log Base 2. – samoz

Hier ist eine andere Art, es zu sagen.

Angenommen, Ihr Algorithmus ist linear in der Anzahl der Stellen in der Größe des Problems. Vielleicht haben Sie also einen neuen Algorithmus, um eine große Zahl zu faktorisieren, die Sie als linear in der Anzahl der Ziffern anzeigen können. Eine 20-stellige Nummer benötigt dabei doppelt so lange wie eine 10-stellige Zahl mit Ihrem Algorithmus. Dies hätte Log-Komplexität. (Und es wäre etwas für den Erfinder wert.)

Bisektion hat das gleiche Verhalten. Es dauert ungefähr 10 Bisektionsschritte, um die Intervalllänge um einen Faktor von 1024 = 2^10 zu verringern, aber nur 20 Schritte werden das Intervall um einen Faktor von 2^20 verringern.

Logkomplexität bedeutet nicht immer, dass ein Algorithmus bei allen Problemen schnell ist. Der lineare Faktor vor dem O (log (n)) kann groß sein. Ihr Algorithmus kann also bei kleinen Problemen furchtbar sein und wird erst dann nützlich, wenn die Problemgröße so groß ist, dass andere Algorithmen einen exponentiellen (oder polynomischen) Tod erleiden.

Quelle

2009-04-15 12:20:10

Gut erklärt mit der großen Problemgröße. –

Wie zu wissen, wenn Big O Logarithmisch ist?

Antwort

Verwandte Themen