什么是大 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)。

Answer 2

答案是O(n^2)。

假设变量 i 是矩阵的行号，j 是列号。使用此循环，您只会查看矩阵的一半。这给你 O(0.5n^2) 的时间复杂度，但这只是 O(n^2).

尝试帮助您理解 O(n log(n))：

O(log(n)) 复杂度算法的一个示例是对已排序的数字列表进行二进制搜索。通过检查中间元素并丢弃列表中明显高于或低于您正在查看的数字的一半，您可以在每次比较时解决一半问题。

对长度均为 n 的 n 个不同集合进行相同的二分查找，时间复杂度为 O(n log(n))。

Answer 3

内循环开始迭代i次，i增加1由外循环控制。

因此内循环会收到外循环的1, 2, 3, ... ,n 并迭代，归结为内循环迭代 1 + 2 + 3 + ... + n = n(n+1)/2

n(n+1)/2 = (n^2)/2 + n/2。此函数的增长由 n^2 主导，因此上限可以表示为 O(n^2).

检查我刚刚运行的模拟。

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

What is the Big O, upper bound of this code

algorithm

complexity-theory

big-o

discrete-mathematics

time-complexity