2.4算法分析-运行时间计算
2021-04-14 12:29
标签：判断 分析 ati 部分 循环 static public int array 一般法则 法则1——for循环 一个for循环的运行时间至多是该for循环内部语句的运行时间乘以迭代次数 法则2——嵌套的for循环 从里向外分析循环，一组嵌套循环内部语句的运行时间为该语句的运行时间乘以该组所有的for循环的大小的乘积。 法则3——顺序语句 将各语句的运行时间求和 法则4——if/else语句 不超过判断的运行时间加上，两部分中运行时间长者 下方代码表面是递归实际上是一个简单的循环，从而其运行时间为O(N) 递归正常使用时，将其转换成一个循环结构是很困难的。 以上例子中同样是计算斐波那契数列第n项 使用数学归纳法易证得 fib(n) = Ω((3/2)n) (n>4) ,fib(n) = O((5/3)n) , 而arr(n) = O(n)，显然fib(n)需要花更多的时间 2.4算法分析-运行时间计算 标签：判断 分析 ati 部分 循环 static public int array 原文地址：https://www.cnblogs.com/TedXiong/p/13337379.html1 public static long factorial(int n) {
2 if (n ) {
3 return 1;
4 } else {
5 return n * factorial(n - 1);
6 }
7 }
1 public long fib(int n) {
2 if (n ) {
3 return 1;
4 } else {
5 return fib(n - 1) + fib(n - 2);
6 }
7 }
8
9 public long arr(int n) {
10 long[] array = new long[n + 1];
11 if (n ) {
12 return 1;
13 } else {
14 array[0] = 1;
15 array[1] = 1;
16 for (int i = 2; i ) {
17 array[i] = array[i - 1] + array[i - 2];
18 }
19 return array[n];
20 }
21 }
上一篇：第七章 多线程
下一篇：Python流程控制