出处： 算法第四版 Edition Sedgewick 著，问题 1.4.7
三道小题初看觉得很简单，但是仔细一分析，a、b小题里面的内循环操作次数是和外层的n、i值有关，并不是简单的操作N次，很久没有算过时间复杂度了，稍微感到有点棘手。
public static void fa(int N) {
int sum = 0; for (int n = N; n > 0; n /= 2) {
for (int i = 0; i < n; i++) {
sum++; } } System.out.println(sum); } public static void fb(int N) {
int sum = 0; for (int i = 1; i < N; i *= 2) {
for (int j = 0; j < i; j++) {
sum++; } } System.out.println(sum); } public static void fc(int N) {
int sum = 0; for (int i = 1; i < N; i *= 2) {
for (int j = 0; j < N; j++) {
sum++; } } System.out.println(sum); } 答案和做法
a小题
如果按照通常的方法，分析for有多少个，那么分析起来会很痛苦，外层循环是 O ( l o g N ) O(logN) O(logN)的操作很容易看出来，但是第二个for，i和n是挂钩的，这个时候通常的方法就不起作用了。
换一种思路，先写一下sum++操作的运行次数
N N/2 N/4 ... 1 ，这实际上是一个等比为2的等比数列，我们把这个数列记为L，它的项数为n
注意到第n项等于1，而L的首项是N，那么 1 = N ∗ 2 1 − n 1=N*2^{1-n} 1=N∗21−n，得出 n = l o g 2 ( N ) + 1 n=log_2(N)+1 n=log2(N)+1
对L用等比公式求和， S n = N ∗ 1 − ( 1 2 ) n 1 − 1 2 S_n=N*\frac{1-(\frac{1}{2})^n}{1-\frac{1}{2}} Sn=N∗1−211−(21)n = N ( 2 n − 1 ) N(2^n-1) N(2n−1)，把n带入，化简即可得到 2 N − 1 2N-1 2N−1
也就是说内循环的总操作次数是2N，那么它其实就是 O ( N ) O(N) O(N)级别的算法
b小题
而L的和 S n = N ∗ 1 − 2 n 1 − 2 S_n=N*\frac{1-2^n}{1-2} Sn=N∗1−21−2n = N ( 2 n − 1 ) = 2 N − 1 N(2^n-1)=2N-1 N(2n−1)=2N−1，
那么b也是 O ( N ) O(N) O(N)级别的算法
c小题
c小题用常规的做法做即可，c是 O ( N l o g N ) O(NlogN) O(NlogN)级别的算法
解释一下a，b同为O(N)级别的算法，为什么它们实际操作次数却不一样，因为O(N)取的是近似值，剩余的较低次项都被忽略了，但是实际计算中低次项的次数同样很关键，因此a,b的执行次数会不一样
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/228935.html原文链接：https://javaforall.net
