大O表示法：如何确定在特定时间复杂度下使用哪种算法？

Question

6

所以当有人要求你提供一个O(n)或O(nlogn)算法来计算某个问题时，你如何知道该怎么回答呢？似乎唯一能够回答这种问题的方法是事先了解各种算法的时间复杂度，而不是即兴想出什么。我正确地假设了吗？

- Parth

1

你可以尝试思考满足约束条件的算法（无论是新算法还是已知算法），并丢弃不符合条件的算法。:-) 你有具体的例子吗？ - ShreevatsaR

6个回答

2

“你是正确的，你应该了解不同算法的时间复杂度才能知道这个问题的答案。你应该知道排序的时间复杂度，查找字典、哈希表、并查集、流图、深度优先搜索、广度优先搜索、最小生成树等的时间复杂度。这些都是基础。算法导论这本书可以很好地帮到你。”

- Amir Rachum

1

但是，你需要知道常见问题的算法复杂度，例如迭代、搜索、排序、哈希表查找等。例如，了解简单排序算法如冒泡排序的时间复杂度为O(n^2)，而快速排序在平均情况下的时间复杂度为O(n log n)非常有帮助。还很重要的是能够快速分析算法以确定其复杂度，并看看如何改进它以使其更快。

- Dima

1

那距离事实并不太遥远。有一些系统的方法，但它们很辛苦，并且最终也经常被“捷径”所取代。

大O表示上限。如果有人问你任何算法而你不知道，你可以说O(n^n)，可能是正确的（尽管还有更慢的算法存在）。当然，它并不是一个紧密的上界。

“捷径”基本上就是一个灵感点，你会在其中发现一些证明特定上界的模式。

99% 的时间，大多数人都只是凭直觉找到一种好的方式来看待算法，然后做足够的工作来证明上界。例如，与其查看执行流程，通常可以说“每个项目最多处理x次，每次花费固定时间”（对于O(n)算法）。可能会错过最多log n个项目被处理的事实，但如果你真正理解算法正在做什么，这种情况相当不可能发生。

当然，这可能无法帮助您通过算法课程。

对于系统化的方法 - 嗯，有“MIT 6.046J / 18.410J 算法导论”课程视频可以在 YouTube 上观看。讲师是一本非常受尊敬的算法教材的作者之一。

- user180247

1

反思一下，我觉得我回答了稍微有点偏离问题。哎，算了。 - user180247

0

这可能比您要查找的内容更加学术，但值得知道的是，对于某些问题，可以证明解决它的任何算法都不会比某些下限更好。例如，比较排序不会做得比O（n log n）更好。另一个例子是汉诺塔，由于问题的构造方式，其任何解决方案都必须是指数级别的。

关于下限的一些讨论在mathoverflow上...为了完整起见而链接，我不知道阅读它有多实际 :D

无论如何，有时候正确的问题是要问，“在给定时间内可以做到吗？”

除此之外，就像其他人说的那样：要具备解决哪些问题所使用的算法的工作知识。 Bobah提供了很好的例子。（只需注意哈希表操作并不总是保证为O（1），但预期如此。）

- johncip

0

我采取的方法更为实用。

我所知道的唯一其他方法是，找到问题的理论复杂度并进行渐近分析。

- krico

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bobah · Accepted Answer

简单情况如下：

遍历列表 - O(n)

单一的二进制或树操作 - O(log n)（这意味着将n个元素插入到树中的时间是n log n）

哈希表操作 - O(1)

NP完全问题（这里需要一些经验来发展直觉）- 通常呈指数增长（但对于许多问题，可以应用有效的启发式算法）

对于具有E边和V顶点的图，复杂度取决于算法的性质和图的密度，表示为F(E,V)。对于良好的DFS/BFS，时间复杂度为E+V。

几乎每个算法都可以分成以上（或类似）小块的集合。当块递归地组合在一起时，如A包含B，复杂度相乘；当块跟随彼此时，如A然后B，复杂度是max（复杂度A，复杂度B）。