算法地复杂度.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使得，当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) 定义：f(n) = O(g(n))表示存在c0,n00使得，当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))表示存在c0,n00使得，当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))表示对任意c0,存在n00使得，当n≥n0时，0 ≤ f(n) cg(n)。 算法复杂度的渐进表示 “ω”类似于“”。直观上，f(n) = ω(g(n))表示f(n)的数量级大于g(n)的数量级。 例如，0.5n3 = ω(n2) 定义：f(n) = Ω(g(n))表示对任意c0,存在n00使得，当n≥n0时，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, c≠1) 常见复杂度排序 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