该算法的时间复杂度
time complexity for this algorithm
for (i = 1; i <= n; i *= 2)
for (j = 1; j <= i; j++)
sum++;
我认为它的时间复杂度是 O(n) (1 + 2 + 2 + 3 + 3 + 3 ... = (1(2^(log2n)-1))/(2-1), 几何数列之和)。这样对吗？我对我的答案感到困惑。
i 更改这些步骤：1, 2, 2^2, ..., 2^log(n) 并且在外循环的每次迭代中，内循环 运行 i 次。因此，时间复杂度 T(n) 是 1 + 2 + 2^2 + ... + 2^log(n) 等于 2^{log(n) + 1} -1。因此，T(n) = Theta(n).
for (i = 1; i <= n; i *= 2)
for (j = 1; j <= i; j++)
sum++;
我认为它的时间复杂度是 O(n) (1 + 2 + 2 + 3 + 3 + 3 ... = (1(2^(log2n)-1))/(2-1), 几何数列之和)。这样对吗？我对我的答案感到困惑。
i 更改这些步骤：1, 2, 2^2, ..., 2^log(n) 并且在外循环的每次迭代中，内循环 运行 i 次。因此，时间复杂度 T(n) 是 1 + 2 + 2^2 + ... + 2^log(n) 等于 2^{log(n) + 1} -1。因此，T(n) = Theta(n).