1）.... + n / 16 + n / 8 + n / 4 + n / n .. =？
2）... + n / 5 + n / 4 + n / 3 + n / 2 ... n / n .. =？
我正在寻找一些算法的时间复杂性，在这些算法中我遇到了几个几何级数。我相信第一几何级数具有log（n）。第二几何级数的时间复杂度是多少？
假设（1）为n *（…+ 1/2 ^ k +…+ 1/16 + 1/8 + 1/4 + 1/2 + 1/1），答案为2n，因为总和1 + 1/2 + 1/4 +…+ 1/2 ^ k +…收敛到值2。要看到这一点：
1/1 + 1/2 + … + 1/2^n + … = k
(1/1 + 1/2 + … + 1/2^n + …)/2 = k/2
1/2 + 1/4 + … + 1/2^(n+1) + … = k/2
k - 1 = k/2
k/2 = 1
k = 2
上面的关键步骤是识别第三行的LHS比第一行的LHS小。
对于（2），n *（…+ 1 / k +…+ 1/5 + 1/4 + 1/3 + 1/2 + 1/1）是谐波序列的n倍。谐波序列发散，因此不确定，趋于无穷大。要看到这一点，请比较两个系列：
1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + …
1/1 + 1/2 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + …
第二个与第一个相同，但是所有术语的分母都增加到下一个更高的2的幂。因此，第二个序列的总和不能大于第一个序列的总和。但是第二个系列显然有所不同，因为我们可以将两个1 / 4s，四个1 / 8s等分组，得到总和1 + 1/2 + 1/2 +…+ 1/2 +…
1）n {（1/1）+（1/2）+（1/4）+（1/8）+ ...} ==> O（n），因为此级数{（1/1） +（1/2）+（1/4）+ ...}等于数字2
2）n {（1/1）+（1/2）+（1/3）+（1/4）+ ...} ==> O（n Lnn），因为此级数{（1/1 ）+（1/2）+（1/3）+ ...}等于Lnn（这是谐波序列）