Dub*_*bby 2 algorithm big-o runtime time-complexity asymptotic-complexity
我试图通过不同的方法找到算法的复杂性.在数学上我遇到了一个O(m + n)和另一个O(mn)方法.但是,我无法掌握或说出这一点.这不像是我看着他们并得到"啊!这就是发生了什么"的感觉!有人可以使用他们自己的例子或任何其他工具解释这个吗？
O(m+n) 例:
for(int i = 0, i < m, i++)
//code
for(int j = 0, j < n, j++)
//code
m迭代的代码发生了.然后n迭代的代码发生.
O(mn) 例:
for(int i = 0, i < m, i++)
for(int j = 0, j < n, j++)
//code
对于每次迭代m,我们都有n迭代的代码.想象一下迭代非方形2D数组.
m并且n不一定等于相同的值.如果他们确实等于相同的值,那么O(m+n):
O(m+n) => O(m+m) => O(2m) => O(m)
我建议看一下这个问题/答案,以便了解最后的过渡.
并为O(mn):
O(mn) => O(mm) => O(m^2)
我对寻找直觉的建议是如下思想实验：
首先，要意识到 m 和 n 是输入 的两个不同测量值。它们可能是两个输入流的长度、矩阵边的长度、或同一数据结构的两个不同属性的计数，例如同一图的边和节点计数，或任何类似的度量。
直觉是，big-O根据一个简单的函数来表达算法的真实运行时间（或其他一些方面，例如比较计数或所需空间）的界限- 调用 R(m, n) - 乘以一些任意常数。我们忽略常数因子，并通过调用它们的运行时间 O( R(m, n) ) 将所有受相同 R 限制的算法视为一个家族。
因此，大 O(m + n) 表示真正的运行时间受某个函数 R(m,n) = C(m + n) 的限制，适用于适当大的 m 和 n。对于图示例，这表示算法的实际运行时间将以顶点和边数之和的倍数为界。
您可以将边界函数视为具有轴 m、n 和 R(m,n) 的 3d 图形。或者你可以想到图表：
R(m,n) = m + n
--------------
m= 1 2 3 4
n=1 1 2 3 4
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
对于 R(m,n) = mn，你有
R(m,n) = mn
--------------
m= 1 2 3 4
n=1 1 2 3 4
2 2 4 6 8
3 3 6 9 12
4 4 8 12 16
作为 3d 图形，第一个函数是平面，第二个函数几乎在所有点上都是增长速度更快的函数。这意味着如果 m 和 n 增长得足够大，那么 O(mn) 边界最终将比 O(m+n) 大（对应于可能更慢的程序），因为常量变得无关紧要。
举一个快速增长成本的例子，假设一个 O(m+n) 算法在其运行时边界中有一个额外的常数因子 3（与上述两种算法相比，它在小输入上可能非常慢）：
R(m,n) = 3(m + n)
--------------
m= 1 2 3 4
n=1 3 9 12 15
2 9 12 15 18
3 12 15 18 21
4 15 18 21 24
所以 O(m + n) 看起来比上图中的 O(mn) 约束更少。但是看看 m=n=100 的情况。这里 O(m + n) 算法的界限是 3(m + n) = 600。但是具有小常数的 O(mn) 算法的界限是 mn = 10000。如果 m 和 n 很大，显然你想要第一个。
@Anonymous 对本文的初始版本提出了一个很好的观点，它混淆了 big-O 和 big-Theta。Big-O 只处理被测量数量的界限或上限。例如，这意味着每个O(n) 算法也是 O(n log n) 和 O(n^2)。如果实际运行时间受限于增长较慢的函数，那么它也受限于所有增长较快的函数。
然而，人们常说“这个算法是 O(n)”，而这意味着边界很紧。也就是说，Cn 是某个常数 C 的运行时间的上限，而 Dn 也是某个其他常数 D（以及适当大的 n）的下限。这种严格的界限被恰当地表述为 Theta(n)，而不是 O(n)。Theta(R(m, n)) 算法的运行时间（粗略地说）与 R(m, n) 成正比。
最后我要补充一点，在很多情况下你不能忽略常量。文献中有很多算法比常用算法渐进“快”，但常数太大，以至于对于实际问题的大小，它们总是太慢。计算几何有很多例子。基数 2 排序是另一个。它是 Theta(n)，但在实践中，一个好的快速排序（Theta(n log n) 平均情况）将在大小至少为 10^8 整数的数组上击败它。