Ist o (n log n) exponentielle Speedup über o (n ^ 2)?

Question

Ich würde gerne wissen, ob $ o (n \ log n) $ eine exponentielle Speedup über $ O (n ^ 2) $ ?

Answer 1

$ o (n \ log n) $ ist ein polynomial beschleunigt über $ o (n ^ 2) $ , insbesondere fast ein quadratic speedup. $ o (n \ log n) $ ist groß-o von $ o (n ^ k $ ) Für alle $ K> 1 $ . Die Laufzeit ist daher zwischen linearer und beliebiger Powerfunktion, deren Exponent streng größer als 1 ist.

Lassen Sie $ f (n)= n \ log n $ . Heben Sie es auf eine Leistung von etwas Werts etwas weniger als 2, um die ursprüngliche Laufzeit anzunähern. Wir schließen ab, $ F (n) \ ca. ^ {2- \ VAREPSILON} (\ \ log n) ^ {2- \ VAREPSILON} $ und in $ o (n ^ 2) $ . Wenn wir quadratisch $ F (n) $ haben, haben wir $ n ^ 2 (\ \ log n) ^ 2 $ , etwas weniger effizient als der ursprüngliche $ n ^ 2 $ , daher ist es grundsätzlich eine quadratische Beschleunigung.

stattdessen $ o (\ log n ^ 2)= o (\ log n) $ ist eine exponentielle Speedup über $ O (n ^ 2) $ . Wenn $ g (n)= 2 \ log (n) $ , dann $ e ^ {g (n)}= n ^ 2 $ .