算法的复杂度有时间复杂度空间复杂度.

时间复杂度并不是表示一个程序解决问题需要花多少时间,而是当问题规模扩大后,程序需要的时间长度增长得有多快。同样,空间复杂度指当问题规模扩大后,程序需要的内存增长得有多快。本文主要讨论一下时间复杂度。

一个算法的复杂度是,而另一个算法的复杂度是,这里的n指的是数据的规模,当数据规模增大的时候,的计算量增长速度要比的计算量增长速度大的多.我们尽可能选择一些复杂度小的算法,比如,等.比较糟糕的算法是复杂度成指数级别增长的,例如

复杂度计算

下面我们根据具体的例子来看一下如何计算算法的复杂度.

O(1)

def test(n):
    i = n*(n+1)/2
    return i

这个例子中无论n如何增大,函数的计算量是一样的,所以该算法的复杂度为O(1)

O(log2n)

def test(n):
    i = 1
    while i<n :
        i = i*2;

    return i

每次循环i都会被乘2,所以i其实是2的t次方,t为循环次数,进而有2^t<n,我们把两边都取对数(计算机相关一般都是以2为底的对数),有t<=log2n,所以这个算法的复杂度为O(log2n)

O(n^2)

def test(n):
    sum = 0
    for i in range(n):
        for j in range(n):
            sum += 1
    return sum

很明显,函数的执行次数是n*n,当n逐渐变大时,算法的执行时间会明显增大.这个算法的复杂度为O(n^2)

常见算法复杂度

算法 复杂度
哈希查找 O(1)
有序数组二分查找 O(logN)
无序数组任意元素查找 O(N)
图遍历算法 O(N)
快速排序算法 O(NlogN)

P问题

如果一个问题可以找到一个能在多项式的时间里解决它的算法,那么这个问题就属于P问题

比如说对一些数进行排序,用快速排序算法复杂度为O(NlogN),再比如计算0~100的和复杂度为O(N)

NP问题

有一些问题无法通过计算得到结果,比如说找质数的问题,你无法通过一个公式计算出下一个质数是多少.

但是我们很容易验证一个数是不是质数.验证过程符合多项式复杂度.

如果我们要找到100以内的质数,可以对100以内的所有数进行验证.从而得到答案.这样的问题属于NP问题

很显然,所有的P类问题都是NP问题。也就是说,能多项式地解决一个问题,必然能多项式地验证一个问题的解。

科学家现在所做的事情,比如说牛顿提出牛顿定律,其实就是找到了多项式解决力学问题,这时NP问题就会变为P问题

关键是,人们想知道,是否所有的NP问题都是P类问题。我们可以再用集合的观点来说明。如果把所有P类问题归为一个集合P中,把所有 NP问题划进另一个集合NP中,那么,显然有P属于NP。现在,所有对NP问题的研究都集中在一个问题上,即究竟是否有P=NP?通常所谓的“NP问题”,其实就一句话:证明或推翻P=NP。

NP-complete问题

NP-complete问题很像物理中的统一场论,我们都知道问题往往可以约化为一个更复杂的问题,比如说解一元一次方程和可以约化到解一元二次方程中,因为一元二次方程比一元一次方程更复杂,他们是包含关系.

换句话说,只要解决了NP-complete问题,那么所有的NP问题都解决了。这种问题的存在难以置信,并且更加不可思议的是,这种问题不只一个,它有很多个,它是一类问题。这一类问题就是传说中的NPC问题,也就是NP-完全问题。NPC问题的出现使整个NP问题的研究得到了飞跃式的发展。我们有理由相信,NPC问题是最复杂的问题。

既然所有的NP问题都能约化成NPC问题,那么只要任意一个NPC问题找到了一个多项式的算法,那么所有的NP问题都能用这个算法解决了,NP也就等于P 了。因此,给NPC找一个多项式算法太不可思议了。因此,前文才说,“正是NPC问题的存在,使人们相信P≠NP”。我们可以就此直观地理解,NPC问题目前没有多项式的有效算法,只能用指数级甚至阶乘级复杂度的搜索。

NP-hard问题

NP-hard问题同样难以找到多项式的算法,但它不一定是NP问题。也就是说NP-hard问题比NPC问题广,即使NPC问题发现了多项式级的算法,NP-Hard问题有可能仍然无法得到多项式级的算法。

咱们把找质数的问题换一个问法:是否有一个公式能够计算出下一个质数?

你会发现验证这个问题都比较困难.所以不属于NP问题.


参考:
什么是P问题、NP问题和NPC问题

posted @ 2018-06-05 16:20:10
评论加载中...

发表评论