___ qstntxt ___

Ich lese das Thema der Algorythmusanalyse. Hier ist der Textausschnitt aus dem Buch

  

Wenn sich n verdoppelt, erhöht sich die Laufzeit linear um den Faktor 2   Programme, 4 für quadratische Programme und 8 für kubische Programme.   Programme, die in logarithmischer Zeit laufen, nehmen nur eine additive Konstante   länger, wenn n sich verdoppelt, und Programme, die in O laufen (n log n)   etwas mehr als doppelt so lange, um unter den gleichen Umständen zu laufen.

     

Diese Erhöhungen können schwer zu erkennen sein, wenn die Terme niedrigerer Ordnung vorhanden sind   relativ große Koeffizienten und n ist nicht groß genug.

Meine Frage ist, was Autor bedeutet, dass Begriffe niedrigerer Ordnung relativ große Koeffizienten haben? Kann jemand mit Beispiel erklären

Danke!

    
___ answer7107229 ___

Die asymptotische Notation bezieht sich auf die Grenzen der Laufzeit als n- & gt; unendlich. Also kann eine Funktion, die O (n log n) ist, eine tatsächliche Laufzeit von .1 * n log n + 100000 * n haben.

In diesem Fall ist der Ausdruck 100000 * n der Ausdruck "niederer Ordnung". Als n- & gt; unendlich wird dieser Term durch den Term .1 * n log n übertroffen.

Wie Sie jedoch sehen können, wird der Wert 100000 * n für kleine n die Laufzeit dominieren.

    
___ tag123algorithm ___ Ein Algorithmus ist eine Folge wohldefinierter Schritte, die eine abstrakte Lösung für ein Problem definieren. Verwenden Sie dieses Tag, wenn sich Ihr Problem auf den Algorithmusentwurf bezieht. ___ answer7107221 ___

Wenn Sie zum Beispiel einen O (n) Algorithmus auf niedrigeren Skalen haben, könnten Sie T (n) = 490239n + (lächerliche Konstante einfügen) haben, was bedeutet, dass die Leistung schlecht aussehen würde, aber wenn die Skalen zunehmen, sehen Sie, dass Anstieg ist immer linear.

Das Beispiel der realen Welt ist merge sort, das O (n logn) -Problem ist, dass die Rekursion einen Rechenaufwand oder Overhead hat, der ein Faktor von n ist, der kleiner ist als nlogn, so dass er im Big-O verworfen wird dass dieser Faktor auch ziemlich groß wird und die Leistung beeinträchtigt.

    
___ answer7107245 ___

Angenommen, Ihr Algorithmus führt %code% Berechnungen tatsächlich aus, wenn er auf %code% -Elementen ausgeführt wird. Jetzt für %code% benötigen Sie 1001 Berechnungen, und für %code% brauchen Sie 2004. Der Unterschied zum linearen Wachstum ist winzig, und Sie können kaum den quadratischen Beitrag erkennen!

Asymptotisch jedoch benötigt Ihr Algorithmus O (n ^ 2) Schritte, so dass asymptotisch (wenn n groß wird) die Verdoppelung der Eingabegröße Ihre Laufzeit vervierfacht. Aber für unseren kleinen Wert hat die Verdopplung von 1 auf 2 die Laufzeit vervierfacht! Der Term niederer Ordnung ist %code% und sein Koeffizient (1000) ist groß im Vergleich zum Koeffizienten des Ausdrucks erster Ordnung %code% (der 1 ist).

Dies zeigt, wie die asymptotische Komplexität nichts über bestimmte, besonders kleine Werte aussagt. Es ist lediglich eine einschränkende Aussage über das Verhalten, wenn %code% groß wird.

    
___ answer7107262 ___

Wenn Sie die O-Notation verwenden, geben Sie den größten Ausdruck der Funktion an, die Ihre Leistungsgrenze ist. Wenn zum Beispiel die Leistung immer durch f = c 3 3 + c <2 n 2 + c <1> n + c <0> , Sie würden sagen, das ist O (n 3 ). Der Autor sagt, dass, wenn n klein ist, die Koeffizienten eine größere Auswirkung als n auf die Leistung haben können, beispielsweise wenn c2 sehr groß und c3 sehr klein ist , scheint die Leistung O (n 2 ) zu sein, bis die Größe von n die Koeffizienten dominiert, wenn man nur die relative Leistung für spezifische kleine Fälle von n betrachtet.

    
___

8

Ich lese das Thema der Algorythmusanalyse. Hier ist der Textausschnitt aus dem Buch

  

Wenn sich n verdoppelt, erhöht sich die Laufzeit linear um den Faktor 2   Programme, 4 für quadratische Programme und 8 für kubische Programme.   Programme, die in logarithmischer Zeit laufen, nehmen nur eine additive Konstante   länger, wenn n sich verdoppelt, und Programme, die in O laufen (n log n)   etwas mehr als doppelt so lange, um unter den gleichen Umständen zu laufen.

     

Diese Erhöhungen können schwer zu erkennen sein, wenn die Terme niedrigerer Ordnung vorhanden sind   relativ große Koeffizienten und n ist nicht groß genug.

Meine Frage ist, was Autor bedeutet, dass Begriffe niedrigerer Ordnung relativ große Koeffizienten haben? Kann jemand mit Beispiel erklären

Danke!

    
venkysmarty 18.08.2011, 12:08
quelle

4 Antworten

4

Wenn Sie die O-Notation verwenden, geben Sie den größten Ausdruck der Funktion an, die Ihre Leistungsgrenze ist. Wenn zum Beispiel die Leistung immer durch f = c 3 3 + c <2 n 2 + c <1> n + c <0> , Sie würden sagen, das ist O (n 3 ). Der Autor sagt, dass, wenn n klein ist, die Koeffizienten eine größere Auswirkung als n auf die Leistung haben können, beispielsweise wenn c2 sehr groß und c3 sehr klein ist , scheint die Leistung O (n 2 ) zu sein, bis die Größe von n die Koeffizienten dominiert, wenn man nur die relative Leistung für spezifische kleine Fälle von n betrachtet.

    
tvanfosson 18.08.2011, 12:16
quelle
9

Angenommen, Ihr Algorithmus führt n^2 + 1000 n Berechnungen tatsächlich aus, wenn er auf n -Elementen ausgeführt wird. Jetzt für n = 1 benötigen Sie 1001 Berechnungen, und für n = 2 brauchen Sie 2004. Der Unterschied zum linearen Wachstum ist winzig, und Sie können kaum den quadratischen Beitrag erkennen!

Asymptotisch jedoch benötigt Ihr Algorithmus O (n ^ 2) Schritte, so dass asymptotisch (wenn n groß wird) die Verdoppelung der Eingabegröße Ihre Laufzeit vervierfacht. Aber für unseren kleinen Wert hat die Verdopplung von 1 auf 2 die Laufzeit vervierfacht! Der Term niederer Ordnung ist n und sein Koeffizient (1000) ist groß im Vergleich zum Koeffizienten des Ausdrucks erster Ordnung n^2 (der 1 ist).

Dies zeigt, wie die asymptotische Komplexität nichts über bestimmte, besonders kleine Werte aussagt. Es ist lediglich eine einschränkende Aussage über das Verhalten, wenn n groß wird.

    
Kerrek SB 18.08.2011 12:14
quelle
2

Die asymptotische Notation bezieht sich auf die Grenzen der Laufzeit als n- & gt; unendlich. Also kann eine Funktion, die O (n log n) ist, eine tatsächliche Laufzeit von .1 * n log n + 100000 * n haben.

In diesem Fall ist der Ausdruck 100000 * n der Ausdruck "niederer Ordnung". Als n- & gt; unendlich wird dieser Term durch den Term .1 * n log n übertroffen.

Wie Sie jedoch sehen können, wird der Wert 100000 * n für kleine n die Laufzeit dominieren.

    
Patrick 18.08.2011 12:13
quelle
0

Wenn Sie zum Beispiel einen O (n) Algorithmus auf niedrigeren Skalen haben, könnten Sie T (n) = 490239n + (lächerliche Konstante einfügen) haben, was bedeutet, dass die Leistung schlecht aussehen würde, aber wenn die Skalen zunehmen, sehen Sie, dass Anstieg ist immer linear.

Das Beispiel der realen Welt ist merge sort, das O (n logn) -Problem ist, dass die Rekursion einen Rechenaufwand oder Overhead hat, der ein Faktor von n ist, der kleiner ist als nlogn, so dass er im Big-O verworfen wird dass dieser Faktor auch ziemlich groß wird und die Leistung beeinträchtigt.

    
Jesus Ramos 18.08.2011 12:12
quelle

Tags und Links