在讨论计算复杂性时，似乎每个人通常都会直接转向BigO。
比方说，例如，我有一个混合算法，例如合并排序，它对较小的子数组使用插入排序(我相信这称为平铺合并排序)。它最终仍会与O(n log n)合并，但是我想讨论一下小n的算法的行为/特征，如果实际上没有合并的话。
出于所有意图和目的，平铺合并排序是插入排序，对我的小n的域执行完全相同的指令。但是，Big O处理大和渐近的情况，而为小n讨论Big O几乎是矛盾的。人们甚至对“在这种情况下表现得像O(n ^ 2)算法”这样的单词大吼大叫。在形式理论计算分析的背景下，在n较小的情况下描述算法行为的正确方法是什么？需要澄清的是，不仅在n小的情况下，而且在n从不大的情况下。
有人可能会说，对于这么小的n没关系，但是我对它有用的情况感兴趣，例如，具有一个较大的常量(例如多次执行)，并且在实际情况下它会显示出明显的趋势并成为现实。主导因素。例如，下图所示的初始二次增长。我并没有解雇Big O，而是要求找到一种方法来恰本地讲述故事的两面。
[编辑]
如果对于“small n”，常数可以轻松消除所有增长率的痕迹，则可以
如果n不是“小”(n足够大以至于增长率不会受到任何实际常数的显着影响)，又还不够大以至于不能显示最终渐近增长率，那么只有子增长率可见(例如上图中的形状)？
没有实用的算法可以表现出这种行为？即使没有，理论上的讨论仍然应该是可能的。我们是不是仅仅因为那是“一个人应该做什么”而测量而不是讨论该理论？如果在所有实际情况下都观察到某种行为，为什么没有理论是有意义的？
让我用另一种方式解决这个问题。我有一张图，显示分段的超线性步骤。听起来很多人会说“这纯粹是巧合，它可以是任何可以想象的形状”(当然是极端的情况)，并且如果它是正弦波，它也不会击打眼睑。我知道在很多情况下形状可以被常量隐藏，但是在这里很明显。我怎样才能正式解释为什么图形产生这种形状？
我特别喜欢@Sneftel的话“不精确但有用的指导”。
我知道Big O和渐进分析不适用。什么是？我可以走多远？
Discuss in chat
最佳答案
重要的是要记住，渐近分析是一种分析简化，而不是分析算法的要求。以选择排序为例。是的，它以O(n^2)时间执行。但是，确实可以精确执行n*(n-1)/2比较和n-1-k交换，其中k是从正确位置开始的元素数量(不包括最大值)。渐近分析是一种简化性能分析(否则通常是不切实际的)任务的工具，如果我们对“真正的n大”部分不感兴趣，可以将其放在一边。
您可以选择表达界限的方式。说一个函数需要精确的n + floor(0.01*2^n)操作。当然，那是指数时间。但是也可以说:“对于不超过10个元素的数据大小，此算法需要在n和2*n之间进行运算。”后者不是描述曲线的形状，而是描述该曲线的包络线，对于特定用例范围内的算法实用性，提供了不精确但有用的指导。