我想知道之间的区别算法的复杂性 和 问题的复杂性 ，也就是哪些点与这两件事不同
最佳答案
好问题!大多数人不区分两者，这是一个很大的禁忌。
简单地说，算法的复杂性 是算法的运行时间。这可以用多种方式表示，大 O、大 Theta 或各种 Landau Notations 中的任何一种。 .还有其他表示，但最常用于大 O 表示法，可用于分析作为输入大小函数的算法的最坏情况时间复杂度。
问题的复杂性 通常是解决问题的任何算法的下限(在这里 wiki 是一个不错的资源)。例如，我们可以证明基于比较的排序的下限为 n log n .这意味着，任何通过比较元素进行排序的算法，无论哪种算法，都至少需要 n log n最坏情况下的时间。使用朗道符号我们会说这个问题需要 Omega(n log n) .
总之，问题复杂度是一个下限，而算法通常会建立一个上限。当您找到一个算法的上限与问题的下限匹配时，您就找到了一个渐近最优算法!
关于time-complexity - 算法的复杂性和问题的复杂性。有什么区别？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44741119/