算法的复杂度.ppt

算法的复杂度,二分查找算法的运行效率,影响二分查找算法的运行效率的因素：,二分查找算法的运行效率,影响二分查找算法的运行效率的因素： 输入规模 (在100个数中查找 vs 在106个数中查找) 硬件平台 (巨型计算机 vs PC机) 输入 (查找23 vs 查找62),二分查找算法的运行效率,影响二分查找算法的运行效率的因素： 输入规模 - 定义算法的复杂度为输入规模的函数 (在100个数中查找 vs 在106个数中查找) 硬件平台 - 渐进表达式 (巨型计算机 vs PC机) 输入 - 分别考虑最坏情况、平均情况、最好情况下算法的复杂度 (查找23 vs 查找62),问题的输入规模,定义算法的复杂度以输入规模为参数。例如， 在n个已排序的数中进行查找，binarySearch算法的复杂度为O(logn) 对n个数进行排序，mergeSort算法的复杂度为O(nlogn),以下算法判断一个数是否为质数，对于输入为n的数，其复杂度为O(n)。 primilityTesting(n) for i = 2 to n 1 if (n % i = 0) return false; return true; 但是，人们认为primilityTesting算法的复杂度远远高于合并排序算法。,算法复杂度的渐进表示,硬件平台影响程序的运行效率，成为比较不同程序效率高低的一个障碍。 通过用渐进符号对程序效率渐进表示，能够消除硬件平台对程序效率的影响。 我们主要学习下面的几个渐进符号 , O,o,算法复杂度的渐进表示,“”类似于“=”。直观上，它表示两个函数在同一个数量级上。 例如，2n2 + 3n - 0.5 = (n2)。 定义：f(n) = (g(n)表示存在c10,c20,n00使得，当nn0时，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) 定义：f(n) = O(g(n)表示存在c0,n00使得，当nn0时，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)表示存在c0,n00使得，当nn0时，0 cg(n) f(n)。,算法复杂度的渐进表示,“o”类似于“0,存在n00使得，当nn0时，0 f(n) < cg(n)。,算法复杂度的渐进表示,“”类似于“”。直观上，f(n) = (g(n)表示f(n)的数量级大于g(n)的数量级。 例如，0.5n3 = (n2) 定义：f(n) = (g(n)表示对任意c0,存在n00使得，当nn0时，0 cg(n) < f(n)。,一些常用的渐进等式,O(1) + O(f(n) = O(f(n) O(1)*O(f(n) = O(f(n) O(f(n) + O(g(n) = O(f(n) if g(n) = O(f(n) = O(g(n) if f(n) = O(g(n) O(logcn) = O(log2n) (c0, c1),常见复杂度排序,O(logn), O(n), 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 + + (2logn-1/n)*logn = = logn + (1/n)*logn 1 = O(logn) 因此，在查找成功的情况下，binarySearch的平均复杂度： O(logn)*O(1) = O(logn),