Question
Je tente de résoudre cette récurrence
T (n) = 3 T (n / 2) + n lg n ..
Je suis venu à la solution qu'il appartient aux maîtres théorème 2 cas puisque nlogn est O (n ^ 2)
mais après avoir fait référence au manuel de solution i remarqué cette solution qu'ils ont
Le soluttion dit que n lg n = O (n ^ (lg 3 - e)) pour e entre 0 et 0,58
Cela signifie donc nlogn est O (n) .. est ce droit? Est-ce que je manque quelque chose ici?
est pas NLGN O (n ^ 2)?
La solution
This will explain things better
Autres conseils
n*log(n)
is not O(n^2)
. It's known as quasi-linear and it grows much slower than O(n^2)
. In fact n*log(n)
is less than polynomial.
In other words:
O(n*log(n)) < O(n^k)
where k > 1
In your example:
3*T(2n) -> O(n^1.585)
Since O(n^1.585)
is polynomial and dominates O(n*log(n))
, the latter term drops off so the final complexity is just O(n^1.585)
.
nlg3 is not O(n). It outgrows O(n)... In fact, any exponent on n that is larger than 1 results in an asymptotically longer time than O(n). Since lg(3) is about 1.58, as long as you subtract less than .58 from the exponent it is asymptotically greater than O(n).