java - 时间复杂度 : While loop with nested for Loop[java]

Question

所以我才刚刚开始学习时间复杂度，我对它有一些“还可以”的把握，但是我对如何处理这个代码段有点困惑。我已经阅读了其他帖子，但我很难掌握事情，除非有人屠杀我要说的话。有点像打自己的脸。

public int example(int[] array) {

    int result = 15;
    int i = array.length;

    while(i > 1)
    {
      for(int x = 0; x < array.length;x++)
      {
        result+= 1;
        result+=2*array[x];
      }
      i = i/2; 
    }
return result;
}

好吧，我只计算算术运算。据我所知，如果我错了(可能是)，请纠正我，

x++ 发生 n 次。

result+= 1 发生 n 次。

result +=3 * array[x] 发生 2n 次

总共4n次

并且 i = i/2 发生 logn 次

那么正确的方程是 4nlogn？？

Answer 1

您在 4n*log(n) 上走在正确的轨道上.但是，请注意，对于大 O 时间复杂度，常量被删除，因此这将是 O(n*log(n)) .

由于大 O 定义，常量被删除:f(x)是O(g(x))如果f(z) <= c*g(z)对于所有 z > 一些数字。这里的关键是 c可以是任何常数。即使你的f(x)是100x你仍然可以拥有 c=200和 g(x)仍然会更大。

作为旁注，由于我们可以分解出常量，因此在计算大 O 时间复杂度时不必计算每个操作。您只需要查看循环。一个发生 n次，其他log(n)次。所以是O(n*log(n)) .代码可以在每个循环内执行 1000 次操作，也可以执行 2 次。因为常量已从我们的大 O 方程中分解出来，所以这个数字无关紧要。只有循环的数量和性质。