beg*_*ggs 16 algorithm performance complexity-theory big-o profiling
最近在一次采访中,我被问到了几个与技术问题过程中出现的各种算法的Big-O有关的问题.我不认为我在这方面做得很好......自从我参加编程课程以来我被要求计算算法的Big-O十年以来,我没有一个关于任何东西的'Big-O'的讨论我一直在努力或设计.我参与了许多与其他团队成员的讨论以及与我一起工作过的关于代码复杂性和速度的架构师的讨论,但我从未参与过在实际项目中实际使用Big-O计算的团队.讨论总是"考虑到我们对数据的理解,有更好或更有效的方法吗？" 从来没有"这个算法的复杂性是什么"？
我想知道人们是否真的在真实的单词中讨论他们的代码的"大O"？
Mit*_*eat 19
它不是那么多使用它,它更多的是你理解其含义.
有些程序员没有意识到使用O(N ^ 2)排序算法的后果.
我怀疑除了那些在学术界工作的人会在日常生活中使用Big-O复杂性分析.
Bri*_*ian 11
没有不必要的n平方
根据我的经验,你没有很多关于它的讨论,因为它不需要讨论.在实践中,根据我的经验,所有发生的事情是你发现某些东西很慢并且看到它是O(n ^ 2)实际上它可能是O(n log n)或O(n),然后你去了更改.除了"那是n平方,去解决它"之外,没有其他讨论.
所以是的,根据我的经验你很常用它,但只是在"减少多项式的阶数"的基本意义上,而不是在一些高度调整的分析中"是的,但如果我们切换到这个疯狂的算法,我们将从logN下降到Ackerman函数的倒数"或者一些这样的废话.任何小于多项式的东西,理论都会从窗口中移出并切换到分析(例如,甚至在O(n)和O(n log n)之间进行判断,测量实际数据).
Big-O表示法相当理论化,而在实践中,您对实际的性能分析结果更感兴趣,这些结果可以为您提供关于性能如何的难以理解的结果.
您可能有两种排序算法,这些算法可以通过本书O(n^2)和O(nlogn)上限进行,但是分析结果可能会显示效率更高的算法可能会有一些开销(这不会反映在您为其找到的理论界限中)以及针对特定问题的设置正在处理,你可能会选择理论上效率较低的排序算法.
底线:在现实生活中,分析结果通常优先于理论运行时边界.
我一直这样做.当您必须处理"大"数字时,通常在我的情况下:用户,数据库中的行,促销代码等,您必须知道并考虑算法的Big-O.
例如,生成用于分发的随机促销代码的算法可用于生成数十亿个代码...使用O(N ^ 2)算法生成唯一代码意味着数周的CPU时间,而O(N)意味着小时数.
另一个典型的例子是代码中的查询(糟糕!).人们查找表然后对每行执行查询...这将订单调到N ^ 2.您通常可以更改代码以正确使用SQL并获得N或NlogN的订单.
因此,根据我的经验,只有在使用正确的算法类之后,分析才有用.我使用分析来捕获不良行为,例如理解为什么"小"数字绑定应用程序表现不佳.