n log n ist O (n)?

Question

Ich versuche, diese Wiederholung zu lösen

T (n)= 3 T (n / 2) + n lg n ..

Ich bin zu der Lösung gekommen, dass es zum Master-Theorem-Fall 2 gehört, da n lg n O (n ^ 2) ist

aber nachdem ich mich auf das Lösungshandbuch bezogen habe, habe ich festgestellt, dass diese Lösung ist

Die Lösung besagt, dass n lg n= O (n ^ (lg 3 - e)) für e zwischen 0 und 0,58 ist

Das bedeutet also, dass n lg n O (n) ist. Ist das richtig?Vermisse ich hier etwas?

Ist nicht nlgn O (n ^ 2)?

Answer 1

Dies wird die Dinge besser erklären

Answer 2

n*log(n) ist kein O(n^2).Es ist als quasi-linear bekannt und wächst viel langsamer als O(n^2).Tatsächlich ist n*log(n) kleiner als das Polynom.

Mit anderen Worten:

O(n*log(n)) < O(n^k)

wobei k > 1

In Ihrem Beispiel:

3*T(2n) -> O(n^1.585)

Da O(n^1.585) polynomisch ist und O(n*log(n)) dominiert, fällt der letztere Begriff ab, sodass die endgültige Komplexität nur O(n^1.585) ist.

Answer 3

n lg3 ist nicht O (n).Es wächst aus O (n) heraus ... Tatsächlich führt jeder Exponent auf n, der größer als 1 ist, zu einer asymptotisch längeren Zeit als O (n).Da lg (3) ungefähr 1,58 ist, ist es asymptotisch größer als O (n), solange Sie weniger als 0,58 vom Exponenten subtrahieren.