算法复杂度指的是最坏情况下的复杂度。

Question

4

我们有最好情况、平均情况和最坏情况下的时间复杂度。因此，当有人询问算法的复杂度时，他指的是什么？

- user567879

我们需要更多的上下文。否则，这可能是其中任何一个。 - flight

1

正如quasiverse所说，可能是其中任何一个。所以如果有人问，就给他们全部。问题解决了 :P - user684934

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dietrich Epp · Accepted Answer

口语：通常是平均情况。这就是为什么人们说快速排序的时间复杂度为O(N log N)，哈希表查找的时间复杂度为O(K)（K = 键大小）。它们的最坏情况分别为O(N^2)和O(K*N)。我建议要明确。

学术上：通常是最坏情况。然而，在学术界，人们通常更感兴趣的是证明给定问题的复杂性类别，而不是研究算法的复杂性。对于学者来说，算法可能只是一个方便的证明复杂性上限的工具，而不是实际的研究对象。

另一个需要注意的是，“平均情况”完全取决于输入分布。大多数人假设均匀分布，除非他们使用“现实世界”的短语，此时他们的输入是任何人的猜测。