复杂度

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

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

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

比如下面示例

//计算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

fib()时间复杂度.png fib(6).png 对比分析.png

有时候算法之间的差距，往往比硬件方面的差距还要大！

• 如果单从执行效率上进行评估可能会想到这么一种方案：

1. 比较不同算法对同一组输入的执行处理时间
2. 这种方案也叫做：事后统计法

上述方案有比较明显的缺点：

• 执行时间严重依赖硬件以及运行时各种不确定的环境因素
• 必须编写相应的测算代码
• 测试数据的选择比较难保证公正性

故一般会从以下维度来评估算法的优劣

• 正确性、可读性、健壮性(对不合理输入的反应能力和处理能力)
• 时间复杂度(time complexity): 估算程序指令(重复执行的代码)的执行次数(执行时间)
• 空间复杂度(space complexity): 估算所需占用的存储空间

大O表示法（Big O）

一般用大O表示法来描述复杂度，它表示的数据规模( n )对应的复杂度

• 忽略常数、系数、低阶

1. 9 >> O(1)
2. zn + 3 >> O(n)
3. n² + 2n + 6 >> O(n²)
4. 4n² + 3n² +22n + 100 >> O(n³)
   写法上，n³等价于n^3

注意：大O表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率

对数阶的细节

对数阶.png

所以log2n、log9n统称为logn

大O也可以称之为：渐进时间复杂度

常见的复杂度：

image.png

https://zh.numberempire.com/graphingcalculator.php

数据规模较小时.png 数据规模较大时.png

算法的优化方向：

• 用尽量少的存储空间
• 用尽量少的执行步骤(执行时间)
• 根据情况，可以采用：空间换时间、时间换空间

多数据规模的情况：比如多入参

多数据规模.png

还有其他复杂度：

• 最好、最坏复杂度
• 均摊复杂度
• 复杂度震荡
• 平均复杂度
• .....

注：比较合理的复杂度分析一般都会从最好情况复杂度、最坏情况复杂度、平均情况复杂度入手

leetcode : 算法交流顶级中文网站 ---> https://leetcode-cn.com/