gpt4 book ai didi

time-complexity - 算法的复杂性和问题的复杂性。有什么区别?

转载 作者:行者123 更新时间:2023-12-01 01:50:46 25 4
gpt4 key购买 nike

我想知道之间的区别算法的复杂性 问题的复杂性 ,也就是哪些点与这两件事不同

最佳答案

好问题!大多数人不区分两者,这是一个很大的禁忌。

简单地说,算法的复杂性 是算法的运行时间。这可以用多种方式表示,大 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/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com