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!
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.
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.
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.
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
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!
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
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.
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.
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.
Tags und Links algorithm