c - 这个循环的时间复杂度

Question

for (int i=0; i<n; i++)
{
 int j = 2;
 while (j<i)
    j = j * j;
}

我认为它的 n*log(n) 作为第一个循环迭代 n 次，但我不确定第二个循环。

Answer 1

由于这个问题具有家庭作业的所有特点，我不会直接给出最终答案，而是给你一些关于如何自己到达那里的指导。

您是对的，您需要对内部循环的迭代次数进行限制以确定总体限制。要对此进行评估，请考虑值的形式 j将接受该循环的连续迭代:2、4、16、256 等。根据循环迭代次数为该数字编写一个封闭公式很有用。

很明显，该序列由 2 的递增幂组成，但不是线性递增的幂。我们有 2¹, 2², 2⁴, 2⁸, ....此时，不过，您应该能够识别该模式，并能够为 j 的值编写一个公式。在k之后内循环的第 th 次迭代，对于 k = 0, 1, 2, 3 .... 让 Inner(k) 指定该公式. (具体公式留作习题。)

那么对于 i 的给定值，将执行多少次内循环迭代？变量 j在循环迭代时采用 Inner(k) 的值，循环在 j >= i 时终止。 ，因此迭代次数是最小值 k 使得 Inner(k) 至少与 i 一样大，并且该循环的最大迭代次数是最小 k 使得 Inner(k) 至少为 n .现在，估计n是 Inner(k)，并求解 k。

其余的细节再次作为练习。