algorithm - 什么是大 O，这段代码的上限

Question

我有点困惑，我已经研究 Big O 时间复杂度几个小时了，并阅读了这里的所有文章。

 int myfunc(int n)
 { int result = 0;
   for (int i = 0; i<n; i++)
     for (int j = i; j>0; j--)
       if (i%j == 0)
         result += j;
   return result;
 }

有人向我展示了这段代码，我想找到这段代码的上界。

现在，根据我目前所学，我假设上限为 O(n^2)，因为这是一个嵌套循环。但是因为 J 链接到 I；我想知道这段代码是否真的是 O(n log n)，我不得不说我并不完全理解 O(n log n) 的概念。但是我理解所有其他符号，例如...O(1),O(n),O(log n),O(n^2),O(n!)。

Answer 1

对于外循环的每次迭代，内循环恰好 i 次。

当 i = 0 时，内循环运行 0 次。

当 i = 1 时，内循环运行 1 次。

当 i = 2 时，内循环运行 2 次。

...

当 i = n-1 时，内循环运行 n-1 次。

因此，内循环运行的总次数 = 0 + 1 + 2 + ... + (n-1) = (n*(n-1))/2 = (n^2-n )/2.

因此，涉及的计算总数 = (n^2 - n)/2。

因此，给定代码的时间复杂度 = O(n^2)。