比如说，一个算法的理论时间复杂度为 O(n 2 )。然而，当它在一些特定或现实的情况下运行时——例如，在 Facebook 社交图谱中，每个人的亲密朋友不能超过 200 个（我知道这不是真的，但我们只是假设）——那么它的复杂性只是线性 O (n) 由于输入的一些特殊特性，即使理论上它仍然是 O(n 2 )。
我相信，我已经在实际案例中看到了算法复杂性的正式名称，但不记得到底是什么。这是一种“真正的复杂性”或“现实的复杂性”之类的东西。有谁知道它是否有一个特殊的名字？还是我只是碰巧想起了梦中的东西？:) 我在技术写作中需要它。谢谢
我认为这种复杂性类没有特殊的名称，因为您的算法的性能很大程度上取决于数据分布。但是，您为某些真实世界数据估算运行时间的方法有一个名称。它被称为平滑分析。
据我所知，没有正式的名称，但“现实世界的平均/最佳/最坏情况复杂性”可能是可以理解的。
只是为了完整性：
最坏情况下的运行时间是 O(n 2 )。
最佳案例运行时间为 O(n) 。
我们不能真正说出给出的平均案例运行时间是多少。
插入排序就是一个例子。当数据已经排序时，它以 O(n) 运行，但在平均/最坏情况下以 O(n 2 ) 运行。
我认为最好的答案是平均情况。您的平均值计算为输入概率的加权平均值，因此如果算法具有a * n + binputI1和c * n^2 + d * n + einputI2的复杂度，则其平均复杂度将为：
AC = p * (a * n + b) + (1 - p) * (c * n^2 + d * n + e)
p输入的概率在哪里I1。如果在实际情况下，输入几乎总是 I1（即p = 1），那么您的平均复杂度将为 O(n)。学术证明倾向于假设输入是均匀分布的（p = 1/2在我的示例中，所有输入都具有相同的发生概率），但是要研究“现实世界”中算法的复杂性，您必须估计实际发生的概率的输入，这可能会改变算法的平均复杂度（尽管它通常不会：在示例中，即使p = 0.99999，平均复杂度仍然是 O(n^2)，尽管因素会改变）。
如果您假设没有人拥有超过 200 个朋友，则您将 的概率隐式设置nb_friends > 200为 0，这会改变您的平均复杂度，即使最佳情况和最坏情况未发生变化。