正如Knuth所说,
我们应该忘记小的效率,大约97%的时间说:过早的优化是所有邪恶的根源.
这是Stack Overflow常常出现的问题,例如"哪个是最有效的循环机制","SQL优化技术？"等问题.(等等).这些优化提示问题的标准答案是分析您的代码并首先查看它是否是一个问题,如果不是,那么您的新技术就不再需要了.
我的问题是,如果某种技术不同但不是特别模糊或混淆,那真的可以被认为是过早的优化吗？
这是Randall Hyde的一篇名为"过早优化的谬误"的相关文章.
这是我在数据结构和每个讲座/ TA讲座的第一门课程,我们谈论O(log(n)).这可能是一个愚蠢的问题,但如果有人能够向我解释它究竟是什么意思,我会很感激!
我正在阅读一篇关于算法的摊销分析的文章.以下是文本摘要.
摊销分析与平均案例分析类似,因为它涉及一系列操作的平均成本.但是,平均案例分析依赖于有关数据结构和操作的概率假设,以便计算算法的预期运行时间.因此,它的适用性取决于关于算法输入的概率分布的某些假设.
平均情况限制并不排除即使输入概率分布的假设有效,人们也会"不幸"并遇到需要超过预期时间的输入的可能性.
我对上述文字片段的疑问是:
在第一段中,平均案例分析如何"依赖于关于数据结构和操作的概率假设？"我知道平均案例分析取决于输入概率,但上述陈述意味着什么？
作者在第二段中的意思是,即使输入分布有效,平均情况也无效？
谢谢!
什么是大O符号？你用它吗？
我猜错了这个大学课:D
有没有人使用它并给出一些他们使用它的真实例子？
我知道有很多关于大O符号的问题,我已经检查过了:
仅举几例.
我知道的"直觉"如何计算它n,n^2,n!等等,但是我完全失去了关于如何计算它是算法log n,n log n,n log log n等等.
我的意思是,我知道Quick Sort n log n(平均)..但是,为什么？合并/梳子等同样的事情
任何人都可以用不太算数的方式解释我,你怎么计算这个？
主要原因是我即将进行大型采访,我很确定他们会要求这种东西.我已经研究了几天了,似乎每个人都有解释为什么冒泡排序是n ^ 2或维基百科上不可读的解释(对我而言)
我是一名程序员,但没有计算机科学背景,所以最近我一直在关注优秀的MIT OpenCourseWare计算机科学和编程入门.在此过程中,问题是:"任何程序是否只使用函数定义和调用,基本算术运算符,赋值和条件在恒定时间内运行？"
我认为答案是肯定的,因为所有这些操作看起来都很简单.但正如你聪明的人可能已经知道的那样,正确的答案是否定的,显然是因为无限期递归的可能性.
似乎我只是不理解"在恒定时间内"的含义.我想象的意思是,这听起来只是意味着一个简单的操作需要花费已知的时间来完成.我接受递归可以导致你的程序永远运行,但不是每个操作仍然需要有限和可测量的时间每个...即使现在有无限数量的它们？或者答案是否意味着无法有效地说两个无限递归程序需要花费相同的时间来运行？
如果有人能给我一个"在恒定时间内"的权威定义及其含义,我将非常感激!
我已经计算了一些东西,它出现在N.
现在我想有一个列表,其中包含0到N个数字.
例:
N = 5
然后, count_list = [1, 2, 3, 4, 5]
我怎么能这样做？
此外,一旦我创建了列表,我想从该列表中随机选择一个数字并使用该数字.
之后,我想从列表的剩余数字(N-1)中选择另一个数字,然后再使用它.
这样就可以了,列表是空的.
我怎样才能做到这一点？
有人能给我一个具有平方根(n)时间复杂度的算法的例子.平方根时间复杂度甚至意味着什么？
Big-O表示法[1]在实践中失败的一些例子是什么？
也就是说:算法的Big-O运行时间何时会预测算法A比算法B快,但实际上算法B运行时会更快？
稍微宽泛一点:何时对算法性能不匹配的理论预测观察到运行时间？非Big-O预测可以基于搜索树中的平均/预期旋转次数,或者排序算法中的比较次数,表示为因子乘以元素的数量.
澄清:
不管有些答案的说法,大O符号是指预测算法的性能.也就是说,这是一个有缺陷的工具:它只谈论渐近性能,并且模糊了常数因素.这样做有一个原因:它意味着预测算法性能,而不依赖于您执行算法的计算机.
我想知道的是:这个工具的缺陷什么时候显示出来？我发现Big-O符号非常有用,但远非完美.有什么陷阱,边缘情况,陷阱？
我正在寻找的一个例子:使用Fibonacci堆而不是二进制堆运行Dijkstra的最短路径算法,得到O(m + n log n)时间对O((m + n)log n),对于n顶点和m边.你期望迟早会从斐波纳契堆中速度增加,但是在我的实验中说速度增加从未实现过.
(实验证据,没有证明,表明在均匀随机边缘权重上运行的二进制堆花费O(1)时间而不是O(log n)时间;这是实验的一个重要问题.另一个需要计算的婊子是预期的调用DecreaseKey的次数).
[1]真的不是失败的符号,而是符号所代表的概念,以及预测算法性能的理论方法.</抗炫学>
在接受的答案上:
我已经接受了一个答案来强调我希望的那种答案.许多不同的答案同样存在:)我喜欢的答案是,它建议了Big-O表示法"失败"时的一般规则(当缓存未命中占据执行时间时),这也可能增加理解(在某种意义上)我不知道如何最好地表达ATM).