04复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度.pdf
《04复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度.pdf》由会员分享,可在线阅读,更多相关《04复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度.pdf(9页珍藏版)》请在三一文库上搜索。
1、04|复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度 file:/F/temp/geektime/数据结构与算法之美/04复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度.html2019/1/15 15:35:12 04|复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度 上一节,我们讲了复杂度的大O表示法和几个分析技巧,还举了一些常见复杂度分析的例子,比如O(1)、O(logn)、O(n)、O(nlogn)复杂度分析。掌握了这些内容, 对于复杂度分析这个知识点,你已经可以到及格线了。但是,我想你肯定不会满足于此。 今天我会继续给你讲四个复杂度分析方面的知识点,最好情况时间
2、复杂度(best case time complexity)、最坏情况时间复杂度(worst case time complexity)、平均 情况时间复杂度(average case time complexity)、均摊时间复杂度(amortized time complexity)。如果这几个概念你都能掌握,那对你来说,复杂度分析这部分内 容就没什么大问题了。 最好、最坏情况时间复杂度 上一节我举的分析复杂度的例子都很简单,今天我们来看一个稍微复杂的。你可以用我上节教你的分析技巧,自己先试着分析一下这段代码的时间复杂度。 / n表示数组array的长度 int find(int arra
3、y, int n, int x) int i = 0; int pos = -1; for (; i = len) / 数组空间不够了 / 重新申请一个2倍大小的数组空间 int new_array = new intlen*2; / 把原来array数组中的数据依次copy到new_array for (int j = 0; j = len时, 即 i = n的时候,for循环进行数组的copy,所以只有这1次的时间复杂度是O(n); 由此可知: 该算法的最好情况时间复杂度(best case time complexity)为O(1); 最坏情况时间复杂度(worst case time
4、complexity)为O(n); 平均情况时间复杂度(average case time complexity), 第一种计算方式: (1+1+.+1+n)/(n+1) = 2n/(n+1) 【注: 式子中1+1+.+1中有n个1】,所以平均复杂度为O(1); 第二种计算方式(加权平均法,又称期望): 1*(1/n+1)+1*(1/n+1)+.+1*(1/n+1)+n*(1/(n+1)=1,所以加权平均时间复杂度为O(1); 第三种计算方式(均摊时间复杂度): 前n个操作复杂度都是O(1),第n+1次操作的复杂度是O(n),所以把最后一次的复杂度分摊到前n次上,那么均摊下来每次 操作的复杂度
5、为O(1) 144赞 姜威 2018-09-27 23:46:07 总结 一、复杂度分析的4个概念 1.最坏情况时间复杂度:代码在最理想情况下执行的时间复杂度。 2.最好情况时间复杂度:代码在最坏情况下执行的时间复杂度。 3.平均时间复杂度:用代码在所有情况下执行的次数的加权平均值表示。 4.均摊时间复杂度:在代码执行的所有复杂度情况中绝大部分是低级别的复杂度,个别情况是高级别复杂度且发生具有时序关系时,可以将个别高级别复杂 度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。 二、为什么要引入这4个概念? 1.同一段代码在不同情况下时间复杂度会出现量级差异,为了更全面,更准确的描述代码
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 04 复杂度 分析 浅析 最好 最坏 平均 均摊 时间
链接地址:https://www.31doc.com/p-5529962.html