Gbe*_*t90 7 algorithm data-structures
是否有图表或表格显示了许多(至少是流行的)数据结构和算法及其运行时间和效率？
我正在寻找的东西是我可以浏览的,并决定哪种结构/算法最适合特定情况.在处理新项目或作为学习指南时,它会有所帮助.
图表或表格不会是特别有用的参考.
如果您打算使用特定的算法或数据结构来解决问题,那么您最好从内到外了解和理解它.这包括了解(并了解如何推导)各自的效率.这并不是特别困难.大多数标准算法具有简单,直观的运行时间一样N^2,N*logN等
话虽这么说,运行时Big-O并不是一切.以排序为例.堆排序具有比快速排序更好的Big-O,但快速排序在实践中表现更好.Big-O中的常数因素也可以产生巨大的差异.
当你谈论数据结构时,对它们来说还有很多东西,而不是眼睛.例如,哈希映射看起来只是一个具有更好性能的树图,但是您可以获得带有树图的其他排序结构.
了解要使用的最佳算法/数据结构是知识体验问题,而不是查找表.
虽然回到你的问题,我不知道有任何这样的参考.尽管如此,做一个人是一个很好的练习.维基百科有关于常见算法/数据结构的相当不错的文章以及一些体面的分析.
我不相信任何这样的清单存在.众所周知的算法和数据结构数量惊人,而且新的算法和数据结构一直在不断发展.此外,这些算法和数据结构中的许多都是专用的,这意味着即使您面前有一个列表,也很难知道哪些适用于您尝试解决的特定问题.
这种清单的另一个问题是如何量化效率.如果你要根据渐近复杂度(big-O)对算法进行排名,那么你可能最终会将某些算法和数据结构逐渐优化,但在算法之前的小输入上实际上很慢,这些算法对于实际案例来说已经很快但可能在理论上并不完美.例如,考虑查找线性时间序列统计的中位数中值算法,其具有如此巨大的常数因子,其他算法在实践中往往更好.或考虑快速排序,在最坏的情况是O(n 2),但在实践中平均复杂度为O(n LG n)和是得多快于其他排序算法.
另一方面,如果您尝试按运行时效率列出算法,列表会产生误导.运行时效率基于机器和输入特定的许多因素(例如位置,输入的大小,输入的形状,机器的速度,处理器架构等).它通常可能是有用的但是在许多情况下,当另一个算法远远优于时,你可能会被数字误导以选择一种算法.
还需要考虑实现的复杂性.许多算法仅存在于论文中,或者具有未优化的参考实现,或者使用的语言不是您正在寻找的语言.如果你发现一个完全符合你想要但却没有实现的Holy Grail算法,那么编写和调试你自己的版本可能是不可能的.例如,如果没有优势的红/黑树实现,你认为你能够自己编写代码吗？Fibonacci怎么样？或者(来自个人经历)van Emde Boas树？通常,选择一个"足够好"但更容易在更复杂的算法上实现的更简单的算法可能是个好主意.
简而言之,我希望这样的表可以存在,真正拥有所有这些信息,但实际上我怀疑它可以以一种有用的方式构建.来自@ hammar评论的维基百科链接实际上非常好,但是学习在实践中使用什么算法和数据结构的最佳方法是通过练习来尝试它们.