算法的复杂度.ppt
《算法的复杂度.ppt》由会员分享,可在线阅读,更多相关《算法的复杂度.ppt(18页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、算法的复杂度,二分查找算法的运行效率,影响二分查找算法的运行效率的因素:,二分查找算法的运行效率,影响二分查找算法的运行效率的因素: 输入规模 (在100个数中查找 vs 在106个数中查找) 硬件平台 (巨型计算机 vs PC机) 输入 (查找23 vs 查找62),二分查找算法的运行效率,影响二分查找算法的运行效率的因素: 输入规模 - 定义算法的复杂度为输入规模的函数 (在100个数中查找 vs 在106个数中查找) 硬件平台 - 渐进表达式 (巨型计算机 vs PC机) 输入 - 分别考虑最坏情况、平均情况、最好情况下算法的复杂度 (查找23 vs 查找62),问题的输入规模,定义算法
2、的复杂度以输入规模为参数。例如, 在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算法的复杂度远远高于合并排序算法。,算法复杂度的渐进表示,硬件平台影响程序的运行效率,成为比较不同程序效率高低的一个障碍。 通过用渐进符号对程
3、序效率渐进表示,能够消除硬件平台对程序效率的影响。 我们主要学习下面的几个渐进符号 , 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)的数量级小于
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 复杂度
限制150内