6

有时我在试图用 O(x) 表示法估计算法的速度时完全被愚弄了，我的意思是，我真的可以指出顺序是 O(n) 还是 O(mxn)，但对于那些是 O(lg( n)) 或 O(C(power n)) 我认为我在那里遗漏了一些东西......那么，对于快速忽略算法的简单估计，你有什么技巧和窍门？

作为我正在寻找的一个例子，这里有一些简单的（可能是错误的，但尽我所能）：

  • O(n)：如果有一个从 1 到 n 的简单循环（或其中几个，但没有嵌套。
  • O(mxn)：另一个嵌套循环，其中限制为 m 和 n。

提前致谢。

4

8 回答 8

7

递归、分而治之的算法通常是 O(logN)。在分治法上循环的算法将是 O(NlogN)。

于 2009-02-10T13:20:38.963 回答
7

这是一篇可能会有所帮助的博客文章：

分解事物并将它们重新组合在一起的成本

那篇文章解释了处理大 O 订单的“主定理”。

于 2009-02-10T13:28:43.810 回答
4

O(lg(n))：如果您的问题在算法的每一步都缩小了 n 的某个比例（通常为 n/2），并且每一步都做了大量的工作。二分搜索是一个很好的例子，因为每一步都通过做恒定的工作量（计算中点并进行一次比较）将问题大小减半。

请注意，n 位于该比例的顶部。这与您的问题大小在每一步减少 1/n 不同。:)

于 2009-02-10T13:21:34.483 回答
1

如果您正在寻找一种快速估计算法运行时间的方法，那么其他答案都很好。如果您想要更详细的答案，我建议您查看“大师定理”。在德语文章中，有一张很好的表格。

编辑： John D. Cook 对主定理做了一个很好的回顾，请参阅链接他的答案。

于 2009-02-10T13:29:02.000 回答
1

关于 Big O Notation的Wikipedia 文章有一个很好的常用函数顺序图表。

于 2009-02-10T13:33:14.503 回答
1

算法的渐近复杂性在实践中很重要，这里有一些我在审查我的或其他人的代码时使用的经验法则。通常实际的计算机算法是许多变量和非平凡数据结构的函数，但让我们假设（仅用于说明）我们的算法 f 基本上以单个整数 X 作为其参数，并且我们希望找到 f 的渐近复杂度X. 假设 f(0) 是微不足道的。然后一般来说：

  • 从 0 到 X 的每个嵌套循环都会为 X 添加一个指数，因此两个循环（一个嵌套在另一个循环中）给出 X**2（二次）。
  • 如果 f(X) 以尾递归方式调用 f(X-1)，它通常对应于迭代，即单个外循环 (O(X))。
  • 我见过作者打算迭代的例程，但是从 0..X 迭代和到 X-1 的尾递归；这些导致二次行为（O（X**2））
  • 如果 f(X) 调用 f(X-1) 两次或更多次，它会产生一个指数算法，你会得到 O(2**X) 。
  • 如果 f(X) 调用 f(X/2) 两次，它在复杂性方面对应于单次迭代（它是一种分而治之的算法）。（根据细节，它会导致 O(X log X) 或 O(X)，但我意识到无论如何我认为它是一次迭代。）
  • 如果 f 使用任何已正确实现的有序数据结构（有序集、优先级堆等），并且该算法在数据结构中添加了大约 X 个对象，则操作为 O(log X)。因此，如果在循环中发生恒定数量的数据结构操作，例如，您将得到 O(X * log X)。
  • 如果有序数据结构未正确实现，则单个操作可能会得到 O(X) 而不是 O(log X)。

一些特殊情况：

  • 通过附加到字符串或内存区域来增长字符串或内存区域的算法在许多语言中会产生 O(X**2) 开销，例如

    for (i = 0; i < X; i++) { s += "foo"; } // quadratic

  • 这个典型的嵌套循环也有 X**2 开销：

    for (i = 0; i < X; i++) { for (j = 0; j < i; j++) { ... } } // quadratic

  • 像 std::set 和 std::map 这样的 C++ STL 容器对几乎所有操作都有 O(log X) 开销

  • strlen(s) 和其他类似的计数算法在返回 X 时有 O(X) 开销
  • memcpy 等导致 O(X)
  • 存在复杂性方面的危险操作，例如通过相等比较从链表中擦除元素，这会产生 O(X) 或更糟
  • 使用基于模板的容器时，请确保比较、排序等操作符快速且没有隐藏的复杂因素
  • 如果您使用引用计数，如果您将最后一个引用删除到长度为 X 的引用的链接列表，则删除引用可能是最坏情况的 O(X) 操作
  • 如果复制对象的例程不平凡并且例如更新全局对象集，那么在面向对象语言中复制复杂的数据结构会产生奇怪的渐近复杂性

只是我的2美分！希望这可以帮助！

于 2009-02-12T06:32:39.080 回答
1

通常会出现像 O(logN) 这样的数据，因为数据大小为 N，但它被组织在例如树的深度为 logN 的树中。如果典型的搜索涉及从根到叶（在更坏的情况下），那么很容易看出算法将是 O(logN)。

没有硬性规定——你只需要查看每个案例，找出最坏的情况，然后计算成本是多少。

于 2009-09-27T07:37:00.360 回答
0

我不喜欢回答自己的问题，但我今天发现了这个并提醒我这个 SO 问题。

http://bigocheatsheet.com/

于 2013-09-07T17:01:25.887 回答