比如说，一个算法的理论时间复杂度为 O(n2)。然而，当它在某些特定或现实的情况下运行时——例如，在 Facebook 社交图中，每个人不能拥有超过 200 个密友(我知道这不是真的，但我们只是假设)——那么它的复杂度只是线性 O (n) 由于输入的一些特殊特性，即使理论上它仍然是 O(n2)。
我相信，我在实际案例中看到了算法复杂度的正式名称，但记不清具体是什么了。它有点像“真正的复杂性”或“现实的复杂性”之类的。有谁知道它是否有专门的名称？还是我只是碰巧想起了梦中的事情？ :) 我在技术写作中需要它。谢谢
最佳答案
我不认为此类复杂性类别有专门的名称，因为您的算法的性能在很大程度上取决于数据分布。但是，您估算某些真实世界数据的运行时间的方法有一个名字；它叫做Smoothed Analysis .
关于algorithm - 现实案例中的复杂性是否有正式名称？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19807788/