主定理证明
请参考该文章: https://wenku.baidu.com/view/993d716a84868762cbaed522.html
主定理理解运用
看完上面的推导证明, 想必对主定理的推导有了一定理解, 那么又如何理解运用呢?
先晒下公式:
公式大致阐明了三种情况:
- f(n) < nlogb a, 则取时间复杂度为O(nlogb a);
- f(n) = nlogb a, 则取时间复杂度为O(nlogb a log k+1 n);
- f(n) > nlogb a, 则取时间复杂度为f(n);
大白话就是: 谁的复杂度高, 总的时间复杂度就以谁为准。
接下来看一下具体例子运用:
- f(n) < nlogb a的情况:
T(n) = 4T(n/2) + n
这个例子中, a = 4, b = 2, f(n) =n, nlogb a = nlog2 4 = n^2;
那么nlogb a = n^2 > n = f(n) ;
nlogb a 大, 他说了算
所以时间复杂度为: nlogb a = n^2。
- f(n) > nlogb a的情况:
T(n) = 2T(n/2) + n^2
这个例子中, a = 2, b = 2, f(n) =n^2, nlogb a = nlog2 2 = n;
那么nlogb a = n < n^2 = f(n) ;
f(n)大, 他说了算
所以时间复杂度为: f(n) = n^2。
- f(n) = nlog b a 的情况稍微要注意一下, 结合用例解释一下:
T(n) = 4T(n/2) + n^2
这个例子中, a = 4, b = 2, f(n) =n^2, nlogb a = nlog2 4 = n^2;
那么nlogb a = n^2 = n^2 = f(n) ;
则时间复杂度为: n^2 logn;
再看一个案例:
T(n) = 2T(n/2) + nlogn
先忽略f(n) 中logn
这个例子中, a = 2, b = 2, f(n) =n, nlogb a = nlog2 2 = n;
那么nlogb a = n = n = f(n) ;
这个时候我们重新看f(n) = nlogn=nlog k n, 则k=1
则时间复杂度为: n log 2 n;
继续看一个案例:
T(n) = 2T(n/2) + n/2
f(n) = n/2 = n ------在n足够大, 这两者在时间复杂度上是等效的;
这个例子中, a = 2, b = 2, f(n) =n, nlogb a = nlog2 2 = n;
那么nlogb a = n = n = f(n) ;
这个时候我们重新看f(n) = nlogn=nlog k n, 则k=1
则时间复杂度为: n log 2 n;
通过以上三个案例, 我们可以总结f(n) = nlog b a的情况如下:
- 如果f(n) 中存在logn, log2 n …等等, 我们都先忽略, 然后时间复杂度在原来的基础上k+1, 即时间复杂度O(n) = nlog k+1 n;
- 如果f(n) 中不存在logn, log2n … 等等, 我们在原来f(n) = n的基础上, 加上logn
即时间复杂度为O(n) = nlog n;
这两种情况其实本质是一样的, 只要判断nlog b a = f(n), 前提是去掉f(n)的logn项,
那么时间复杂度O(n) = nlog b a log k+1 n
如果k为 0, 即nlog 0 n = n
k 为 1, 即nlog 1 n = nlogn
通过以上学习, 想必你也掌握了主定理的证明理解及运用了吧!
