算法的复杂度.ppt

《算法的复杂度.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法的复杂度二分查找算法的运行效率影响二分查找算法的运行效率的因素：二分查找算法的运行效率影响二分查找算法的运行效率的因素：输入规模(在100个数中查找vs在106个数中查找)硬件平台(巨型计算机vsPC机)输入(查找23vs查找62)二分查找算法的运行效率影响二分查找算法的运行效率的因素：输入规模---定义算法的复杂度为输入规模的函数(在100个数中查找vs在106个数中查找)硬件平台---渐进表达式(巨型计算机vsPC机)输入---分别考虑最坏情况、平均情况、最好情况下算法的复杂度(查找23vs查找62)问题的输入规模定义算法的复杂度以输入规模为参数。例如，在n个已排序的数中进

2、行查找，binarySearch算法的复杂度为O(logn)对n个数进行排序，mergeSort算法的复杂度为O(nlogn)以下算法判断一个数是否为质数，对于输入为n的数，其复杂度为O(n)。primilityTesting(n){fori=2ton–1if(n%i==0)returnfalse;returntrue;}但是，人们认为primilityTesting算法的复杂度远远高于合并排序算法。算法复杂度的渐进表示硬件平台影响程序的运行效率，成为比较不同程序效率高低的一个障碍。通过用渐进符号对程序效率渐进表示，能够消除硬件平台对程序效率的影响。我们主要学习下面的几个渐进符号Θ

3、,O,Ω,o,ω算法复杂度的渐进表示“Θ”类似于“=”。直观上，它表示两个函数在同一个数量级上。例如，2n2+3n-0.5=Θ(n2)。定义：f(n)=Θ(g(n))表示存在c1>0,c2>0,n0>0使得，当n≥n0时，0≤c1g(n)≤f(n)≤c2g(n)。如果算法A的复杂度为Θ(n2)，算法B的复杂度为Θ(n3)。对于规模足够大的问题，算法A的运行时间一定比算法B的运行时间短，与A、B各自的运行平台无关。算法复杂度的渐进表示“O”类似于“≤”。直观上，f(n)=O(g(n))表示f(n)的数量级小于等于g(n)的数量级。例如，2n2+3n-0.5=O(n2)，5n=O(n2

4、)定义：f(n)=O(g(n))表示存在c>0,n0>0使得，当n≥n0时，0≤f(n)≤cg(n)。算法复杂度的渐进表示“Ω”类似于“≥”。直观上，f(n)=Ω(g(n))表示f(n)的数量级大于等于g(n)的数量级。例如，2n2+3n-0.5=Ω(n2),0.5n3=Ω(n2)定义：f(n)=Ω(g(n))表示存在c>0,n0>0使得，当n≥n0时，0≤cg(n)≤f(n)。算法复杂度的渐进表示“o”类似于“<”。直观上，f(n)=o(g(n))表示f(n)的数量级小于g(n)的数量级。例如，5n=o(n2)定义：f(n)=o(g(n))表示对任意c>0,存在n0>0使得，当n

5、≥n0时，0≤f(n)”。直观上，f(n)=ω(g(n))表示f(n)的数量级大于g(n)的数量级。例如，0.5n3=ω(n2)定义：f(n)=Ω(g(n))表示对任意c>0,存在n0>0使得，当n≥n0时，0≤cg(n)0,c≠1)常见复杂度排序O(logn),O(n

6、),O(nlogn),O(n2),O(2n)最坏情况下的复杂度对于所有可能的规模为n的问题，算法的最长运行时间。binarySearch算法最坏情况下的复杂度为O(logn)。最好情况下的复杂度对于所有可能的规模为n的问题，算法的最短运行时间。binarySearch算法在最好情况下的复杂度为O(1)。平均情况下的复杂度对于所有可能的规模为n的问题，算法在平均情况下的运行时间。以binarySearch为例，学习算法在平均情况下的复杂度。平均情况下的复杂度在查找成功的情况下，binarySearch的平均循环次数：(1/n)*1+(2/n)*2+(4/n)*3+(8/n)*4+…+

7、(2logn-1/n)*logn==logn+(1/n)*logn–1=O(logn)因此，在查找成功的情况下，binarySearch的平均复杂度：O(logn)*O(1)=O(logn)å=-niiinlog112/1