Big O.不确定for循环的更新如何影响它

Question

关于for循环的更新如何影响BIG O，我有点困惑

在这样的代码上：

  public static void bigO(int n){
    for(int i=n; i>1; i=i/2){
      for (int j=n; j>1; j=j/2){
        sum++;
      }
    }
  }

我不确定更新(j=j/2)会如何影响它。

Answer 1

两个for循环彼此独立，因此总复杂度应该大致是两个循环的复杂性的乘积。每个循环都是O(lgN)，其中lg表示“log base 2”。因此，将这两者相乘会产生O(lgN*lgN)的整体复杂性。

要了解更好的O(lgN)，请考虑n=16的输入值。然后for中的外部i循环将进行以下迭代：

i  | iteration #
16 | 1
8  | 2
4  | 3
2  | 4

lg(16)实际上等于4，因为2^4 = 16，所以这证实了我们期望的复杂性。您也可以测试其他n值来说服自己。 j中的内环行为相同，并且独立于i中的外环。