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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public static int sum1(int n){
    int result =0;
    for(int i =0;i<=n;i++){
        result+=i;
    }
    return result;
}

public static int sum2(int n){
    return (1+n)*n/2;
}

• 如果单从执行效率上进行评估，可能会想到这么一种方案。比较不同算法对同一组输入的执行处理时间，这种方案也叫做：事后统计法
• 上述方案有比较明显的缺点
  • 执行时间严重依赖硬件以及运行时各种不确定的环境因素
  • 必须编写相应的测算代码
  • 测试数据的选择比较难保证公正性
• 一般从以下维度来评估算法的优劣
  • 正确性、可读性、健壮性（对不合理输入的反应能力和处理能力）
  • 时间复杂度（time complexity）：估算程序指令的执行次数（执行时间）
  • 空间复杂度（space complexity）：估算所需占用的存储空间

大O表示法（Big O）

• 一般用大O表示法来描述复杂度，它表示的是数据规模 n 对应的复杂度
• 忽略常数、系数、低阶
• 9 » O(1)
• 2n + 3 » O(n)
• n² + 2n + 6 » O(n 2 )
• 4n ³ + 3n²+ 22n + 100 » O(n³)
• 写法上，n³ 等价于 n^3
• 注意：大O表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率

对数阶的细节

对数阶一般省略底数，不管是怎么以什么为底的对数，都是可以乘以一个常数，最后转化为以2为底的对数。所以在计算时间复杂度时，对数都统称为logn。 $$ \log_2n=\log_29*log_9n $$

常见的时间复杂度

查看函数图像的网站：https://zh.numberempire.com/graphingcalculator.php

数据规模对比

时间复杂度分析

斐波那契数列，下面有两种解法。递归和非递归。其实可以发现递归的时间复杂度是更高的，当是具规模越大的时候，递归就会越耗时。所以一般都不要使用递归，但是使用了递归也是可以优化的，例如：尾递归，备忘录优化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#时间复杂度O(2^n)
public static int fib1(int n){
    if(n<=1) return n;
    return fib1(n-2)+fib(n-1);
}

#时间复杂度O(n)
public static int fib2(int n){
    if(n<=1) return n;
    int first = 0;
    int second = 1;
    while(n>1){
        second+=first;
        first=second+first;
    }
    return second;
}

多个数据规模的情况

1
2
3
4
5
6
7
8
9

public static void multi(int n,int l){
    for(int i=0;i<n;i++){
        System.out.println(i);
    }
    
    for(int i=0;i<k;i++){
        System.out.println(i);
    }
}

时间复杂度：O(n+k)

算法的优化方向

• 用尽量少的存储空间
• 用尽量少的执行时间
• 空间换时间 OR 时间换空间