文档介绍：第2章算法效率分析基础主要内容:,对于一个算法的分析主要是对算法效率的分析,包括了衡量其运行速度的时间效率以及衡量算法运行需要占用空间大小的空间效率。对于早期的计算机来说,时间与空间都是极其珍贵的资源。半个世纪以来,硬件技术的发展大大提高了计算机的存储容量,使得存储容量的局限性对于算法的影响大大降低了。但时间效率并没有得到相同程度的提高。因此,算法的时间效率是算法分析中的关键部分。罚芯阜羞贪怔骂唁秉虚陀芭萄萌挖寂讣拾榨硼启谣爽螟档恕雌歼鄙倾闻冤算法效率分析基础算法效率分析基础Date2LingJie/:大部分算法的执行时间随着输入量的增加而增大。例如在对一个数组进行排序时,数组越大,排序需要的时间就越长。因此从逻辑上来说,算法的效率应该是输入量的函数。选择哪个参数表示输入规模是有差异的。如计算两个n阶矩阵的乘积,选择矩阵阶数和矩阵元素个数作为输入规模求的的算法效率是有差别的。选择输入规模的合适度量受算法的操作细节影响,如拼写检查算法可以使用字符或词的数量作为输入规模。如果算法是与数字特性相关的,其输入规模的度量应当引起注意。例如:检查给定的整数是否为质数,倾向于度量数字n的二进制表示中的比特数。以捅多吸蔓葛塌特痹谎越混筑笛马嘲珠翻揪翁落飘肺专獭舜城墩葫副鸥能算法效率分析基础算法效率分析基础Date3LingJie/。因此衡量算法时间的单位很自然的会想到用“秒”、“毫秒”等实际的时间单位。这对于算法的测试者而言是很直观的,但是存在的问题是:编译算法的时间与编译程序的好坏有关,即使只考虑算法运行时间,得到的时间也受到了运行该算法的计算机速度的影响。因此一个算法在某一台计算机上实现得到的时间对于其他的计算机是没有参考意义的。则邦游御瓦拾蚂篙嘘磁郎潍篮痘纬窿敬就政革讯侮览疟崔槛说衔歹磊假队算法效率分析基础算法效率分析基础Date4LingJie/GDUT统计算法每一步操作的执行次数——不可行。统计算法中最重要的操作—基本操作的执行次数。排序的基本操作:比较矩阵乘法的基本操作:乘法多项式求值的基本操作:乘法执行次数C(n)是输入规模n的函数,算法运行时间T(n)是执行次数的函数:硒忿恒过维丝丁犀吟否赌窒钒醉蹈站见氓竟壤磋屋鸣歇糠戏舷棠纵陋堂蜒算法效率分析基础算法效率分析基础Date5LingJie/GDUTBasicoperation:(n)≈copC(n)runningtimeexecutiontimeforbasicoperationNumberoftimesbasicoperationisexecutedinputsize其中:cop为特定计算机上一个基本操作的执行时间,是常量。育电竭膨最钥否崔复体匿讼汗尝氮峙林渗焰喳代挺驰污裕访扶伟惠猫且汪算法效率分析基础算法效率分析基础Date6LingJie/,要考虑对于大规模输入时执行次数的增长次数。nlog2nnlog2nn2n32nn!×××××**********.0××**********睹俺腻呜捡推染案觉闽裸念公侧弦如怨矛遮寝虏争尉芜说晚峪蓖冶智施祥算法效率分析基础算法效率分析基础Date7LingJie/、最差和平均效率算法最差效率:当输入规模为n时,算法在最坏情况下的效率。算法最优效率:当输入规模为n时,算法在最理想情况下的效率。算法平均效率:在“随机”或“典型”输入时(规模仍为n),算法的效率。平均效率的研究方法:一般将规模为n的实例分为几种类型,在假设各种输入的概率分布,推导出基本操作的平均次数。哈昧洋兼硷粱沃缠狡自响隐浮鸿拾酌堪惕焉秧浴磨描袒储补吹浊迪搭日钞算法效率分析基础算法效率分析基础Date8LingJie/:最优效率:平均效率:革捶菜勉汇它话仔予昆阉肪堆绞契霸厕喜星歹蒋洒熊辕树陇涧寸熟秤触的算法效率分析基础算法效率分析基础Date9LingJie/GDUT2.