为了方便或更简单的外观而使用较高的 Big-O 表示法值是否常见？
例如：我正在查看此处简要解释的“分片间隙雕刻”算法（第 66 页）。如果我理解正确，算法将采用n最大的任何间隙大小，sum from 1 to n但在同一个文档中它说：
该技术不适用于具有大间隙的碎片文件。如果 n 是 bh 和 bz 之间的簇数，那么在最坏的情况下，在成功恢复之前可能需要 n^2 个对象验证。
所以我的问题是：我对算法的理解是错误的，还是最坏情况下的运行时间被四舍五入n^2到看起来比总和更好？
问问题
420 次
3 回答
2
“从 1 到 n 的总和”确实等于 (n + 1) * n / 2，或 (n^2 / 2 + n / 2)
因此，n^2在这种情况下，数量级是。没有简化（您显然可以删除像 1/2 这样的乘法常数，并且n << n^2当 n 很大时。
于 2014-08-26T07:27:14.607 回答
1
回答实际问题：是的，它不仅很常见，而且非常普遍。O(N*N) 意味着对于某些未指定的 c，度量（通常是运行时）上升速度不快于 c * N *N。显然，随着 N 的增加，N*N + N 小于 2 * N * N，所以 O(N*N + N) 就是 O(N*N)。
于 2014-08-26T07:33:02.850 回答
1
O(f) 中给出的函数 f 是算法复杂度的上限。这意味着对于大小为 n（大于某个大小 n0）的所有输入，您的算法不会使用比 const*f(n) 更多的时间（或空间）。
这意味着如果您的算法执行 sum(i, i=0...n) 步骤（等于 n*(n-1)/2 并且是二次函数），则 const * n*n 是有效的上限所有 n>n0 --> 复杂度为 O(n^2)
另一个解释看这里： big o notation in plain English
于 2014-08-26T07:40:53.037 回答