讨论小n的计算复杂性的正确方法
joz*_*yqk 6 algorithm big-o computation-theory
在讨论计算复杂性时,似乎每个人都会直接进入Big O.
让我们说例如我有一个混合算法,如合并排序,它使用插入排序较小的子阵列(我相信这称为平铺合并排序).它仍然最终与O(n log n)合并排序,但我想讨论小n的算法的行为/特征,在没有实际合并的情况下.
对于所有意图和目的,平铺合并排序是插入排序,对我的小n的域执行完全相同的指令.然而,Big O处理大型和渐近的情况并且讨论小O的Big O几乎是矛盾的.在这种情况下,人们甚至认为"行为就像一个O(n ^ 2)算法",对我大吼大叫".在形式理论计算分析的背景下,在小n的情况下描述算法行为的正确方法是什么？为了澄清,不仅在n很小的情况下,而且在n从不大的情况下.
有人可能会说,对于这么小的n并不重要,但我对它的情况感兴趣,例如有一个很大的常数,例如被执行多次,并且在实践中它会显示出明显的趋势并且是主导因素.例如,下图中显示的初始二次增长.我不是在解雇Big O,更多的是要求一种正确告诉双方故事的方法.
[ 编辑 ]
如果对于"小n ",常数可以很容易地去除所有生长速率的痕迹
- 只讨论了渐近的情况,在这种情况下,与任何实际应用的关联性较小,或者
- 必须有一个阈值,我们同意n不再是"小".
那么n不是"小"的情况(n足够大,以至于增长率不会受到任何实际常数的显着影响),但还不足以显示最终的渐近增长率,因此只能看到子增长率(例如上图中的形状)？
是否没有表现出这种行为的实用算法？即使没有,理论上的讨论仍然是可能的.我们是否仅仅因为"应该做什么"来衡量而不是仅仅讨论理论？如果在所有实际案例中都观察到某种行为,为什么不存在有意义的理论呢？
让我转向另一个问题.我有一个显示分段超线性步骤的图表.听起来很多人会说"这是一个纯粹的巧合,它可以是任何可以想象的形状"(当然极端)并且如果它是一个正弦波而不会击打眼睑.我知道在很多情况下,形状可以被常数隐藏,但这里很明显.我怎样才能正式解释图形产生这种形状的原因？
我特别喜欢@Sneftel的话"不精确但有用的指导".
我知道Big O和渐近分析不适用.什么是？我能走多远？
在聊天中讨论
重要的是要记住,渐近分析是一种分析简化,而不是分析算法的任务.例如,选择排序.是的,它会O(n^2)及时执行.但它也是如此,它执行精确的n*(n-1)/2比较和n-1-k交换,其中k是从正确位置开始的元素数量(除了最大值).渐近分析是一种简化性能分析(否则通常是不切实际的)任务的工具,如果我们对"真正的大n"段不感兴趣,我们可以放弃.
你可以选择表达你的界限.假设一个功能需要精确的n + floor(0.01*2^n)操作.当然,那是指数时间.但也可以说"对于最多10个元素的数据大小,这种算法需要在操作n和2*n操作之间." 后者不是描述曲线的形状,而是围绕该曲线的包络,在特定的用例范围内给出关于算法实用性的不精确但有用的指导.
对于小n,计算复杂性 - 当n向无穷大增加时事物如何变化 - 没有意义,因为其他效应占主导地位.
我已经看过的论文讨论了n的小值的行为,通过测量实际系统上的算法来实现,并讨论算法在实践中的表现而不是理论观点.例如,对于您添加到帖子中的图表,我会说'此图表演示了整体的O(N)渐近行为,但每个图块内的增长是有界的二次'.
我不知道从理论角度讨论这种行为会有意义的情况 - 众所周知,对于小n来说,实际效果超过了缩放的影响.