O (n log n) Speedup esponenziale sopra o (n ^ 2)?

Question

vorrei sapere se $ o (n \ log n) $ è una velocità esponenziale su $ o (n ^ 2) $ ?

Answer 1

$ o (n \ log n) $ è un polinomiale velocità sopra $ o (n ^ 2) $ , in particolare quasi a quadratico Speedup. $ o (n \ log n) $ è big-o di $ o (n ^ k $ ) per tutti $ k> 1 $ . Il suo runtime è quindi tra lineare e qualsiasi powerfunction il cui esponente è strettamente maggiore di 1.

Let $ F (n)= n \ log n $ . Sollevalo a una potenza di un valore leggermente inferiore a 2 per approssimare il runtime originale. Concludiamo $ f (n) \ circa n ^ {2- \ varepsilon} (\ log n) ^ {2- \ varepsilon} $ e in $ o (n ^ 2) $ . Se piangiamo $ f (n) $ , abbiamo $ n ^ 2 (\ log n) ^ 2 $ , leggermente meno efficiente rispetto all'originale $ n ^ 2 $ , quindi è fondamentalmente una velocità quadratica.

invece, $ o (\ log n ^ 2)= o (\ log n) $ è una velocità esponenziale sopra $ O (n ^ 2) $ . Se $ G (n)= 2 \ log (n) $ , quindi $ e ^ {g (n)}= n ^ 2 $ .