Leo*_*uza 5 complexity-theory time-complexity computation-theory space-complexity
我想知道一个算法的复杂度和一个问题的复杂度之间的区别，也就是这两个东西的不同点
小智 5
好问题！大多数人对两者没有区别，这是一个很大的禁忌。
简单来说，算法的复杂度就是算法的运行时间。这可以用多种方式表示，大 O、大 Theta 或任何各种兰道符号。还有其他表示形式，但最常用的是大 O 表示法，它可用于分析算法的最坏情况时间复杂度作为输入大小的函数。
问题的复杂性通常是解决该问题的任何算法的下限（维基百科是一个不错的资源）。例如，我们可以证明基于比较的排序的下限为n log n。这意味着，任何通过比较元素进行排序的算法，无论哪种算法，n log n在最坏的情况下都至少需要时间。使用朗道表示法，我们会说这个问题需要Omega(n log n)。
总之，问题复杂性是一个下限，算法通常会建立一个上限。当您找到一个其上限与问题的下限相匹配的算法时，您就找到了渐近最优算法！
| 归档时间： |
|
| 查看次数： |
1004 次 |
| 最近记录： |