解释大 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

O(n^2) 中的第一段代码运行s 如您所说，因为 limit 的大小为 n^2
然而，第二个 j/=2 每次将 limit 的长度除以 2，因此循环将运行 k 次其中 k=log(n^2) = 2log(n) 因此它是 O(log(n)) 阶
第三个是第一个和第二个的组合，运行秒O((n^2)*log(n))时间

解释大 O 循环和数组

Interpreting Big O Loops and arrays

java

arrays

time

big-o