算法复杂度分类

NP类问题的定义问题:-所有基于决策的问题的集合进入了NP问题的划分中, 这些问题无法在多项式时间内解决或产生输出, 但需要在多项式时间内进行验证。 NP类包含P类作为子集。 NP问题难以解决。

注意:-术语“ NP”并不表示“非多项式”。最初, 该术语表示“非确定性多项式。它表示将根据一个输入数量产生输出。

P类问题的定义:-基于决策的问题集划分为P个问题, 这些问题可以在多项式时间内求解或产生输出。 P问题容易解决

多项式时间的定义:-如果我们在给定的时间内(例如一分钟, 几小时内)根据给定的输入产生输出。这称为多项式时间。

非多项式时间的定义:-如果我们根据给定的输入产生输出, 但没有时间限制, 则称为非多项式时间。但是会产生输出, 但是时间尚未确定。

基于决策的问题的定义:-如果问题的输出为简单的“是”或“否”(或者你可能需要此为true / false, 0/1, 接受/拒绝), 则该问题称为决策问题。将许多优化问题称为决策问题。例如, 如果存在任何哈密顿循环, 则给定曲线G =(V, E)的Greedy方法D.P.。

NP-hard类别的定义:-在这里你要满足以下几点才能进入NP-hard的划分

  1. 如果我们可以在多项式时间内解决这个问题, 那么我们可以在多项式时间内解决所有NP问题
  2. 如果你在多项式时间内将问题转换为一种形式再转换为另一种形式

NP-完全分类的定义:-如果NP-完全存在问题

  1. 在NP中
  2. NP难

所有NP类的图形表示, 包括NP, NP-hard和NP-complete

算法复杂度分类

图:复杂度等级

微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?