【数据结构与算法】复杂度知识

什么是算法？

算法是用于解决特定问题的一系列的执行步骤。

以下算法是为了解决两数相加的问题。

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

以下算法是为了解决 n个数字的和 的问题。

// 1+2+3+...+n
public static int sum(int n){
    int result = 0;
    for(int i = 1; i <= n; i++){
        result += I;
    }
    return result;
}

使用不同算法，解决同一个问题，效率可能相差非常大。
比如：求第 n 个斐波那契数（fibonacci number）

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

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

比较不同算法对同一组输入的执行处理时间
这种方案也叫做：事后统计法
上述方案有比较明显的缺点：

执行时间严重依赖硬件以及运行时各种不确定的环境因素
必须编写相应的测算代码
测试数据的选择比较难保证公正性
一般从以下维度来评估算法的优劣：

正确性、可读性、健壮性（对不合理输入的反应能力和处理能力）
时间复杂度（time complexity）
估算程序指令的执行次数（执行时间）
空间复杂度（space complexity）
估算所需占用的存储空间
由于现在硬件发展的较好，一般情况下我们更侧重于时间复杂度。

大O表示法（Big O）

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

忽略常数、系数、低阶：

9 >> O(1)
2n + 3 >> O(n)
n2 + 2n + 6 >> O(n2)
4n3 + 3n2 + 22n + 100 >> O(n3)
写法上，n3 等价于 n^3
注意：大O表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率。

对数阶的细节

对数阶一般省略底数

log29 ∗ log9n >> log2n
所以 O(log2n) 、O(log9n) 统称为 O(logn)

常见的复杂度

20200326125216195.png 20200326125550303.png 20200326125519876.png

多个数据规模的情况

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

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