复杂度

2022-06-16 本文已影响0人水中的蓝天

本文源自本人的学习记录整理与理解，其中参考阅读了部分优秀的博客和书籍，尽量以通俗简单的语句转述。引用到的地方如有遗漏或未能一一列举原文出处还望见谅与指出，另文章内容如有不妥之处还望指教，万分感谢。

使用不同算法，解决同一个问题，效率可能相差非常大。

那么如何评判一个算法的好坏？

比如下面示例


//计算a和b的和
public static int plus (int a , int b) {
return a +b ;
}

----------------------------------------------- 

//计算1+2+3........+n的和

public static int sum (int n) {

int result = 0;

for (int i = 1; i <= n; i++){

result += i;

}

return result ;

}

比如：求斐波那契数

时间复杂度：O(2^n)
 //递归计算 n: 数组下标 
   public static int fib(int n) {
       
    //如果n小于等于1；就直接返回，否则会死循环
    if (n <= 1) {
        return n;
    }
    //n = (n - 1) + (n - 2)
    return fib(n-1) + fib(n-2);

 }

----------------------------------------------- 

时间复杂度：O(n)
//循环计算
   public static int fib1(int n) {
       
    //如果n小于等于1；就直接返回，否则会死循环
    if (n <= 1) {
        return n;
    }
    
    int  first = 0;//第一个数
    int second = 1;//第二个数
    //需要循环n-1次
    for (int i = 0; i < n - 1; i++) {
        
     int sum = first + second;
     first = second;
     second = sum;
        
    }
    
    return second;

 }

----------------------------------------------- 
时间复杂度：O(n)
//循环计算
   public static int fib1(int n) {
       
    //如果n小于等于1；就直接返回，否则会死循环
    if (n <= 1) {
        return n;
    }
    
    int  first = 0;//第一个数
    int second = 1;//第二个数
    //需要循环n-1次
        while(n-- > 1) {
     second = first + second; //第三个数
     first = second - first;    //第三个数减去第一个数等于第二个数
    }
    return second;

 }

--------------------------

使用线性代数，特殊方程来解；不过可读性会差一些

同样传入44
第一种递归算法耗时：4秒多
第二种循环算法耗时：几乎为0

同样传入46
第一种递归算法耗时：9秒多
第二种循环算法耗时：几乎为0

同样传入97
第一种递归算法耗时：-898760秒多
第二种循环算法耗时：几乎为0