complexity-theory - 确定给定代码段最坏情况下的时间复杂度

Question

确定最坏情况下的时间复杂度。（显示计算）

  int i = 1;
  int j = 4;
  while (i<(n*n)&& j<(n*n*n*n)){
    if (i%3 == 0) i+=3; 
    else i+=4;

    if (j%2 == 0) j*=4;
    else j*=2;          
 }

Answer 1

在最坏的情况下，这将在 i 达到 n^2 或 j 达到 n^4 的任何一端运行。变量 i 线性增加，j 每次迭代都呈指数增加。j 每次迭代只是变成 4 的不同幂。

我将在 n^2/3 次迭代后达到 n^2，即 O(n^2)。j 将在 log_4 n^4 次迭代后达到 n^4（其中 log_4 是对数基数 4）。

所以问题是 n^2 或 log(n^4) 哪个更大，答案是响亮的 n^2。

因此这个算法是 O(n^2)