java - 解释大 O 循环和数组

Question

所以，我知道我的想法是错误的，但我对所有三段代码的回答是它们的复杂度是 O(n^2)。

谁能告诉我我是否错了？

如果是的话，你能帮我想想如何解决类似的问题吗？预先感谢您!

    public static int firstLoop(int[] arr) { 

       int sum = 0; int n = arr.length; 
       int limit = n * n; 
       for ( int j = 0; j < limit; j += 2 ) { 
          sum = (sum + arr[j / n] ) % 100; 
      } 
   return sum; }


     public static int withLoop(int[] arr) { 

    int sum = 0; int n = arr.length; 
    int j = 1; 
    int limit = n * n; 
    for ( j= limit - 1; j > 0; j /= 2 ) { 
    sum = (sum + arr[j / n] ) % 100; } 
    return sum; }

   public static int fwLoop(int[] arr)

    {  int sum = 0; 
      int n = arr.length; 
      int limit = n * n; 
      for ( int k = 0; k < limit; k += 2 ) { 
       int t = 1; for ( j = limit - 1; j > 0; j /= 2 ) { 
       t = (t + arr[j / n] ) % 100; 
      } sum = (sum + t + arr[k / n] ) % 200; 
    } return sum; 
 }

Answer 1

1. 正如您所说，第一段代码的运行时间为 O(n^2)，因为 limit 的大小为 n^2

2. 第二个执行j/=2，每次将limit的长度除以2，因此循环将运行k次，其中k=log(n^2) = 2log(n)，因此它的顺序是O(log(n))

3. 第三个是第一个和第二个的组合，它的运行时间为O((n^2)*log(n))时间