算法的复杂性和问题的复杂性。有什么区别？
Complexity of algorithms and complexity of problems. What are the differences?
我想知道一个算法的复杂度和一个问题的复杂度的区别，即，哪一点两者不同
好问题！大多数人不区分两者，这是一个很大的禁忌。
简单来说，算法的复杂度就是算法的运行时间。这可以用多种方式表示，big O、big Theta 或各种 Landau Notations 中的任何一种。还有其他表示法，但最常用的是大 O 表示法，可用于分析算法的最坏情况时间复杂度作为输入大小的函数。
问题的复杂性 通常是解决该问题的任何算法的下限（wiki 在这里是不错的资源）。例如，我们可以证明基于比较的排序的下限为 n log n。这意味着，任何通过比较元素排序的算法，无论是哪种算法，在最坏的情况下至少需要 n log n 时间。使用 Landau 表示法，我们会说这个问题需要 Omega(n log n)。
总而言之，问题复杂度是一个下限，而算法通常会建立一个上限。当您找到上限与问题下限匹配的算法时，您就找到了渐近最优算法！
我想知道一个算法的复杂度和一个问题的复杂度的区别，即，哪一点两者不同
好问题！大多数人不区分两者，这是一个很大的禁忌。
简单来说，算法的复杂度就是算法的运行时间。这可以用多种方式表示，big O、big Theta 或各种 Landau Notations 中的任何一种。还有其他表示法，但最常用的是大 O 表示法，可用于分析算法的最坏情况时间复杂度作为输入大小的函数。
问题的复杂性 通常是解决该问题的任何算法的下限（wiki 在这里是不错的资源）。例如，我们可以证明基于比较的排序的下限为 n log n。这意味着，任何通过比较元素排序的算法，无论是哪种算法，在最坏的情况下至少需要 n log n 时间。使用 Landau 表示法，我们会说这个问题需要 Omega(n log n)。
总而言之，问题复杂度是一个下限，而算法通常会建立一个上限。当您找到上限与问题下限匹配的算法时，您就找到了渐近最优算法！