我想知道算法的复杂度和问题的复杂度之间的区别,也就是说,这点与这两件事有所不同
最佳答案
好问题!大多数人在这两者之间没有区别,这是一个很大的禁忌。
简而言之,算法的复杂度是算法的运行时间。这可以用多种方式表示,大O,大Theta或各种Landau Notations。还有其他表示形式,但最常用的是大O表示法,可用于分析算法最坏情况下的时间复杂度(取决于输入大小)。
问题的复杂度通常是解决该问题的任何算法的下限(此处wiki是不错的资源)。例如,我们可以证明基于比较的排序具有n log n
的下限。这意味着,在最坏的情况下,无论哪种算法,通过比较元素进行排序的任何算法都将至少花费n log n
时间。使用Landau表示法,我们可以说此问题采用Omega(n log n)
。
总而言之,问题的复杂性是一个下限,算法通常会确定一个上限。当找到上限与问题下限匹配的算法时,就发现了一种渐近最优算法!
关于time-complexity - 算法的复杂性和问题的复杂性。有什么区别?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/44741119/