algorithm - 讨论小 n 计算复杂度的正确方法

Question

在讨论计算复杂性时，似乎每个人通常都会直接转向 Big O。

例如，我有一个混合算法，例如合并排序，它对较小的子数组使用插入排序(我相信这称为平铺合并排序)。它最终仍然是 O(n log n) 的合并排序，但我想讨论小 n 算法的行为/特征，在实际不需要合并的情况下地方。

就所有意图和目的而言，分块合并排序是插入排序，对我的小 n 域执行完全相同的指令。然而，大 O 处理大和渐近的情况，并且针对小 n 讨论大 O 几乎是矛盾的。人们对我大喊大叫，因为我什至认为“在这种情况下表现得像一个O(n^2) 算法”。在正式的理论计算分析的背景下，在小 n 情况下描述算法行为的正确方法是什么？澄清一下，不仅仅是在 n 很小的情况下，而且在 n 永远不会很大的情况下。

有人可能会说，对于如此小的 n 来说，这并不重要，但我对它确实如此的情况很感兴趣，例如对于一个大常量，例如被执行多次，以及在哪里在实践中，它将显示出明显的趋势并成为主导因素。例如下图中的初始二次增长。我不是在驳斥 Big O，更多的是寻求一种正确讲述故事双方的方法。

---

[编辑]

如果对于“小n”，常数可以很容易地消除所有增长率的痕迹，那么要么

1. 仅讨论渐近情况，在这种情况下与任何实际应用的相关性较低，或者
2. 必须有一个我们同意 n 不再“小”的阈值。

如果 n 不是“小”(n 足够大以至于增长率不会受到任何实际常数的显着影响)，但不是但大到足以显示最终的渐近增长率，所以只能看到子增长率(例如上图中的形状)？

是否没有表现出这种行为的实用算法？即使没有，理论上的讨论仍然是可能的。我们测量而不是讨论理论纯粹是因为那是“一个人应该做的”吗？如果在所有实际案例中都观察到某些行为，为什么不能有有意义的理论？

---

让我把问题反过来。我有一个显示分段超线性步骤的图表。听起来很多人会说“这纯粹是巧合，它可以是任何可以想象的形状”(当然是极端的)，如果它是正弦波，他们也不会眨眼。我知道在许多情况下形状可能 被常量隐藏，但在这里很明显。我如何正式解释图形产生这种形状的原因？

我特别喜欢@Sneftel 的话“不精确但有用的指导”。

我知道大 O 和渐近分析不适用。什么是？我能走多远？

Discuss in chat

Answer 1

对于较小的 n，计算复杂性 - 随着 n 向无穷大增加而发生的变化 - 没有意义，因为其他效应占主导地位。

我看过的论文通过在真实系统上测量算法来讨论 n 值较小时的行为，并讨论了算法在实践中的表现，而不是从理论的角度。例如，对于您添加到帖子中的图表，我会说“该图表总体上展示了 O(N) 渐近行为，但每个图 block 内的增长是有界二次方”。

我不知道从理论角度讨论此类行为会有意义的情况 - 众所周知，对于较小的 n，实际效果超过缩放效果。