做公益活动的网站,百事通做网站,jsp网站开发实例视频教程,医院网站建设要素这篇文章是时间复杂度分析的第二篇。在前一篇文章中#xff0c;我们从0推导出了为什么要用时间复杂度#xff0c;时间复杂度如何分析以及时间复杂度的表示三部分内容。这篇文章#xff0c;是对一些常用的时间复杂度进行一个总结#xff0c;相当于是一个小结论
1.常见的大O…这篇文章是时间复杂度分析的第二篇。在前一篇文章中我们从0推导出了为什么要用时间复杂度时间复杂度如何分析以及时间复杂度的表示三部分内容。这篇文章是对一些常用的时间复杂度进行一个总结相当于是一个小结论
1.常见的大O阶
1.1线性阶
一般含有非嵌套循环就是单层循环涉及线性阶线性阶就是随着输入规模的扩大对应计算次数呈直线增长例如下面的代码
public static void main(String[] args) {int sum 0;int n 100;for (int i 1; i n ; i) {sum i;}System.out.println(sumsum);}
上面这段代码它的循环的时间复杂度为O(n)因为循环体中的代码需要执行n次
1.2平方阶
一般嵌套循环就是双层循环属于这种时间复杂度 public static void main(String[] args) {int sum 0;int n 100;for (int i 1; i n ; i) {for (int j 1; j n ; j) {sum i;}}System.out.println(sumsum);}
上面这段代码n100也就是说外层循环每执行一次内层循环就执行100次那总共程序想要从这两个循环中出来就需要执行100*100次也就是n的平方次所以这段代码的时间复杂度是O(n^2)
1.3立方阶
一般三层嵌套循环属于这种时间复杂度
public static void main(String[] args) {int x 0;int n 100;for (int i 1; i n ; i) {for (int j 1; j n ; j) {for (int k 1; k n ; k) {x ; }}}System.out.println(xx);}
上面这段代码n100也就是说外层循环每执行一次中间循环循环就执行100次中间循环每执行一次最内层循环需要执行100次那总共程序想要从这三个循环中出来就需要执行100*100*100次也就是n的立方所以这段代码的时间复杂度是O(n^3)
1.4对数阶
对数属于高中数学的内容我们分析程序以程序为主数学为辅所以不用过分担心。 public static void main(String[] args) {int i 0;int n 100;while (in){i i*2;}System.out.println(ii);}
分析
由于每次i*2之后就距离n更近一步。我们假设有x个2相乘后大于n那么x个2相乘后就会退出循环。那么就有公式2^xn得到xlog(2)n。所以这个循环的时间复杂度为O(logn)
问为什么底数可以忽略答对于对数阶由于随着输入规模n的增大不管底数为多少他们的增长趋势是一样的所以我们会忽略底数。其实就是找输入规模n与执行次数之间的抽象关系抓取主要的忽略次要的
下面给出表和图可以体会一下增长趋势 1.5常数阶
一般不涉及循环操作的都是常数阶因为它不会随着n的增长而增加操作次数。例如︰ public static void main(String[] args) {int n 100;int i n2;System.out.println(ii);}
上述代码不管输入规模n是多少都执行2次根据大O推导法则常数用1来替换所以上述代码的时间复杂度为O(1)
1.6小结
下面是对常见时间复杂度的一个总结 他们的时间复杂度从高到低依次是 O(1)O( log(n) )O(n)O(n*log(n))O(n^2)O(n^3)
根据前面的折线图分析我们会发现从平方阶开始随着输入规模的增大时间成本会急剧增大所以我们的算法尽可能的追求的是O(1)O(log(n))O(n),O(n^log(n))这几种时间复杂度而如果发现算法的时间复杂度为平方阶、立方阶或者更复杂的那我们可以分为这种算法是不可取的需要优化。
2.函数调用的时间复杂度分析
之前我们分析的都是单个函数内算法代码的时间复杂度接下来我们分析函数调用过程中时间复杂度。
2.1几个案例 案例一
public static void main(String[] args) {int n 100;for (int i 0; i n; i) {show(i);}}public static void show(int i){System.out.println(i);}
在main方法中有一个for循环循环体调用了show方法由于show方法内部只执行了一行代码所以show的时间复杂度为O(1)那main方法的时间复杂度就是O(n)
案例二
public static void main(String[] args) {int n 100;for (int i 0; i n; i) {show(i);}}public static void show(int i){for (int j 0; j i; j) {System.out.println(i);}}
在main方法中有一个for循环循环体调用了show方法由于show方法内部也有一个for循环所以show方法的时间复杂度为O(n)那main方法的时间复杂度为O(n^2)
案例三
public static void main(String[] args) {int n 100;for (int i 0; i n; i) {show(i);}for (int i 0; i n; i) {for (int j 0; j n; j) {System.out.println(j);}}}public static void show(int i){for (int j 0; j i; j) {System.out.println(i);}}
在show方法中有一个for循环所以show方法的时间复杂度为o(n)在main方法中show(n)这行代码内部执行的次数为n第一个for循环内调用了show方法所以其执行次数为n^2第二个嵌套for循环内只执行了一行代码所以其执行次数为n^2,那么main方法总执行次数为nn^2n^22n^2n。
根据大O推导规则去掉n保留最高阶项并去掉最高阶项的常数因子2所以最终main方法的时间复杂度为O(n^2) 2.2最坏情况
从心理学角度讲每个人对发生的事情都会有一个预期比如看到半杯水有人会说︰哇哦还有半杯水哦但也有人会说∶天哪只有半杯水了。一般人处于一种对未来失败的担忧而在预期的时候趋向做最坏的打算这样即使最糟糕的结果出现当事人也有了心理准备比较容易接受结果。假如最糟糕的结果并没有出现当事人会很快乐。 算法分析也是类似假如有一个需求∶ 有一个存储了n个随机数字的数组请从中查找出指定的数字。
public static void main(String[] args) {int a search(5);System.out.println(a);}public static int search(int num){int[] arr {11,5,3,6,7,15,6,9};for (int i 0; i arr.length; i) {if (num arr[i]) {return i;}}return -1;}
最好情况 查找的第一个数字就是期望的数字那么算法的时间复杂度为O(1)
最坏情况 查找的最后一个数字才是期望的数字那么算法的时间复杂度为O(n)
平均情况 任何数字查找的平均成本是O(n/2) 最坏情况是一种保证在应用中这是一种最基本的保障即使在最坏情况下也能够正常提供服务所以除非特别指定我们提到的运行时间都指的是最坏情况下的运行时间。
3.小结
这篇文章我们总结了一些常见的大O阶然后给出了相应的表格这属于是一种结论可以记下来的。然后我们分析了函数调用时的时间复杂度其实和之前的分析方法是一样的。最后我们讲了一下最坏情况的分析。
至此算法的时间复杂度的讲解已经完毕了。如果有失误的地方敬请各位指出谢谢大家
