共计 3283 个字符，预计需要花费 9 分钟才能阅读完成。
Example 1 For 循环
思考以下代码的工夫复杂度是多少，应用 Big Theta 示意
public static void printParty(int N) {for (int i = 1; i <= N; i = i * 2) {for (int j = 0; j < i; j += 1) {System.out.println("hello");
int ZUG = 1 + 1;
}
}
}选取一项最具代表性的操作
System.out.println("hello);记其执行次数为 c(N) , 枚举 N 从 1 到 N，C(N)的值，用以下表格示意:
察看高低两个图可知
当 N = 1 时，i = 1, j = 0;
当 N = 2 时，i = 1 , 2, j = 0, 1;
N = 2, 已知 i = 1 的后果，只需再求 i = 2 的后果再将后面算得的 i = 1 的后果相加, 即 3 = 1 + 2
当 N = 3 时，因为 i 的变动是每次变为 2i，即当 N = 2 时，2i = 4，3 比 4 小，循环依然终止在 N = 2，也就是说 N = 3 与 N = 2 的打印次数雷同
……
因而察看得悉，当 N 位于相邻的 2 的某指数幂之间时，打印次数与前一次雷同，且等于后面所有 2 的指数幂时的打印次数相加，即
$$
C(N) = 1 + 2 + 4 + 8 + …… + N
$$
假如 N 为 2 的指数幂，那么上述式子共有 \(1 + log_{2}N \)项
应用等比数列求和公式
$$
S_{n} = \frac{a_{1}(1 – q^{n})}{1 – q}
$$
可算得:
$$
C(N) = \frac{1 – 2^{1 + log_{2}N}}{1 – 2} = 2N – 1
$$
因而 \(C(N) = \Theta(N) \)
技巧 2
察看 N 的值能够发现，C(N)的值总是位于 0.5N 到 2N 之间，因而能够大抵得出 C(N)的函数图像:
不难发现 \(C(N) = \Theta(N) \)
最初,Josh 老师心愿咱们不要一看到 for 循环嵌套就认为工夫复杂度是 \(\Theta(N^{2}) \), 还是要循序渐进地剖析，对于求工夫复杂度的普遍性办法是
- 找出准确的和
- 写例子
- 画图
Example 2 递归树
思考以下函数
public static int f(int n) {if (n <= 1)
return 1;
return f(n-1) + f(n-1);
}工夫复杂度是多少?
Solution 1
当 n = 4 的时候，f(4)的调用状况如图:
计算 f(n)的调用次数 c(n):
C(1) = 1
C(2) = 1 + 2
C(3) = 1 + 2 + 4
…….
C(N) = 1 + 2 + 4 + … + \(2^{N – 1} \)
因而依据等比数列前 N 项和可得 \(C(N) = 2^{N} – 1 \)
除了间接由等比数列前 N 项和得出后果之外，还能够由后面的公式
$$
C(Q) = 1 + 2 + 4 + … + Q = 2Q – 1
$$
此处 \(Q = 2^{N – 1} \)，因而
$$
C(Q) = 2Q – 1 = 2 \cdot 2^{N – 1} – 1 = 2^{N} – 1
$$
也能够得出后果
因而工夫复杂度 \(f(N) = \Theta(2^{N}) \)
Solution 2
从直观上来看，当 f(n)中 n = 4 时，f(4)的调用状况为
当 n = 5 时，f(5)的调用状况为
可见调用次数翻倍，n 每减少 1，调用次数 x 2，因而直观上来说也是 \(2^{N} \)指数级减少，更确切来说:
C(1) = 1
C(N) = 2C(N - 1) + 1
= 2(2C(N - 2) + 1) + 1
= 2(2(2C(N - 3) + 1) + 1) + 1
......
= 2(...2C(N - (N - 1)) + 1 ).... + 1
= 2^(N - 1)C(1) + 1 + 2 + 4 + ... + 2^((N - 1) - 1)
= 2^(N - 1) + 2^(N - 2) + 2^(N - 3) + ... + 4 + 2 + 1
= 2^N - 1工夫复杂度 \(f(N) = \Theta(2^{N}) \)
Example 3 BinarySearch
接下来咱们剖析二分查找的工夫复杂度，二分查找原理都应该比拟相熟了，不再过多介绍，具体实现过程能够查看这个 slide BinarySearch Demo。
直观剖析
咱们晓得的是每进行一次二分查找，其查找范畴都会减半，也就是以后数组的大小减半，假如数组原始大小为 N，最坏的状况下，直到数组大小缩短为 1 时，也就是只剩下一个元素时，咱们才找到想要查找的值，那么，设二分查找的调用次数为 C , 则
$$
1 = \frac{N}{2^{C}}
$$
从而解得
$$
C = log_{2}{N}
$$
而对于二分查找，其函数体内执行次数均为常数阶，因而能够用调用次数来示意工夫复杂度，从直观上来说 \(f(N) = \Theta({log_{2}N}) \)
准确剖析
思考以下问题: 对于一个大小为 6 的数组，应用二分查找，其最坏的状况下，函数的调用次数是多少?
答案是 3 次
那么这是在 N = 6 时的状况，咱们把 N 的所有状况与对应的 函数调用次数 C(N)列出:
可见是一颗递归二叉树，察看可知
$$
C(N) = ⌊log_{2}(N)⌋+1
$$
咱们失去了函数调用次数 C(N)与数组大小 N 的准确关系，那么问题是
\(C(N) = \Theta(log_{2}N) \)吗？
证实:
$$
⌊f(N)⌋=\Theta(f(N))
$$
proof：
$$
f(N) – \frac{1}{2} \le ⌊f(N) – \frac{1}{2}⌋ \le f(N) + \frac{1}{2}
$$
依据 Big Theta 的定义，可知 \(⌊f(N) – \frac{1}{2}⌋领有下界 f(N) – \frac{1}{2} 和上界 f(N) + \frac{1}{2}，属于 f(N)函数簇 \)，因而
$$
⌊f(N)⌋=\Theta(f(N))
$$
抛下常数阶，可知 \(C(N) = \Theta(log_{2}N) \)
不加证实地，咱们还能晓得
$$
⌈f(N)⌉=\Theta(f(N))
$$
$$
log_{P}(N) = \Theta(log_{Q}(N))
$$
因而当前无论是以任何常数为底的对数，都简写为 logN，
因而最终化简后果是 \(C(N) = \Theta(logN) \)
另一种办法计算工夫复杂度
考虑一下下面 Example 2 的一种利用式子自身的递归个性解题的办法，对于二分查找:
二分查找代码的瑕疵
当咱们的二分查找实现代码为:
static int binarySearch(String[] sorts, String x, int lo, int hi)
if (lo > hi) return -1;
int m = (lo + hi) / 2;
int cmp = x.compareTo(sorted[m]);
if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);
else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi);
else return m;
}
存在一个瑕疵，当计算两头地位 m 的时候:
$$
m = \frac{(lo + hi)}{2}
$$
\(当 lo + hi > 2^{31} – 1 \)时，即超过了 int 的最大值时，会产生溢出，导致 m 变成正数，从而引发数组ArrayIndexOutOfBoundsException
因而求两头地位的解决方案是
int mid = low + ((high - low) / 2);或者
int mid = (low + high) >>> 1;在 C 和 C ++ 中 没有 >>>，能够写成
mid = ((unsigned int)low + (unsigned int)high)) >> 1;细节十分重要！
参考
Example 4 MergeSort
本例剖析归并排序的工夫复杂度
归并排序即把一个数组一分为二，再二分为四，四分为八，直至放大为一个数组只有 1 个元素，是一种典型的分治思维。之后再把数组从最底层的开始合并，合并的过程能够参考
MergeSortDemo
因为一次合并即相当于把大小为 N 的数组填充结束，因而以填充次数而言，合并过程的工夫复杂度为 O(N)
直观剖析
把一个大小为 N 的数组一直一分为二直至放大为一个数组只有 1 个元素，如果进行了 K 次划分，那么
\(K = log_{2}N\)
接着剖析每一层的工作量，
第一层，须要将两个大小为 N / 2 的数组合并，工作量为 N
第二层，两个 N / 2 的数组别离由两个 N / 4 的数组合并而来，即 4xN/4，工作量为 N
……
察看知每一层的工作量均为 N，共有 K 层，则总的工作量为
$$
f(N) = K\cdot N=Nlog_{2}N
$$
应用递推的数学公式
因而，归并排序的工夫复杂度为 \(\Theta(NlogN)\)
