是否有一个关于所有东西的Big-O符号的主列表？

Question

17

是否有一个包含所有内容的大O符号的主列表？数据结构、算法、执行的操作，平均情况、最坏情况等。

- raldi

6个回答

6

Cormen book更多地是教你如何证明一个给定算法的Big-O，而不是死记硬背算法和它的Big-O性能。前者比后者更有价值，需要你付出投资。

- Alan

2

尝试阅读Cormen、Leisersen和Rivest所写的“算法导论”。如果它不在那里，那可能不值得了解。

- Oliver Hallam

2

在C++中，STL标准由算法的大O特征和空间需求定义。这样你就可以在竞争性STL实现之间切换，仍然知道你的程序具有相同的运行时特征。特别好的STL实现甚至可以特殊处理特定类型的列表比标准要求更好。

它使得选择特定问题的正确迭代器或列表类型变得容易，因为你可以轻松权衡空间消耗和速度。

当然，大O只是一个指导方针，所有常数都被移除了。如果算法以k*O(n)运行，则会被分类为O(n)，但如果k足够高，则对于某些n和m的值，它可能比O(n^2)更糟糕。

- Soraz

0

对于任何从谷歌搜索进入这个问题的人。

- Rohit Tigga

0

算法导论第二版，也称CLRS（Cormen，Leiserson，Rivest，Stein），是我能想到的最接近的东西。

如果这不行，那么尝试Knuth的计算机程序设计艺术。如果这些都没有，你可能需要做一些真正的研究。

- tgamblin

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

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

- ephemient · Accepted Answer

算法和数据结构字典是一个相当全面的列表，其中包括算法描述中的复杂度（大O符号）。如果您需要更多信息，可以在链接的参考文献中找到，或者作为备选方案，您也可以去Wikipedia查阅。