算法复杂度

2019-12-18 本文已影响0人张_何

算法优劣评估

正确性、可读性、健壮性
时间复杂度: 估算程序指令的执行次数（执行时间）
空间复杂度: 估算所需占用的存储空间

算法复杂度表示法

算法复杂度一般采用大O(ou)表示法
大O表示法是一种粗略的估算方法,通常会忽略常数，系数，低阶
例如：
9 ≈ O(1); 所有常数都认为是O(1)
2n+3≈ O(n)；忽略低阶和常数
5n^2 + 2n + 6≈ O(n^2); 忽略低阶和常数,采用最高阶并忽略系数
3n^3 + 5n^2 + 10n + 100≈ O(n^3)；忽略低阶和常数,采用最高阶并忽略系数
对数阶一般省略底数，log2(n)、log9(n)统称logn
例如：
log2(n) = log2(9) * log9(n); 通过换底公式得到的
用大O表示法就表示为O(logn)
换底公式： formula
常见复杂度

执行次数	复杂度	非正式术语
12	O(1)	常数阶
2n + 3	O(n)	线性阶
4n^2 + 2n + 6	O(n^2)	平方阶
4log2n + 25	O(logn)	对数阶
3n + 2nlog3n + 15	O(nlogn)	nlogn 阶
4n^3 + 3n^2+22+100	O(n^3)	立方阶
2^n	O(2^n)	指数阶

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

数据规模较小时

数据规模较小时 .png

数据规模较大时

数据规模较大时.png

算法的优化方向

用尽量少的存储空间
用尽量少的执行步骤
根据情况可以以空间换时间，或以时间换空间

怎么估算算法的复杂度

假设计算机执行每一条指令的时间都是一样的

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

对于上面的这个函数
外部for循环 i = 0 执行1次，i<n执行n次、i++执行n次
内部整个for循环执行n次
对于内部for循环每次执行，j = 0执行一次，j < n执行n次，j++执行n次，System.out.println()执行n次
总体加起来就是 1+n+n+n*(1+n+n+n) = 3n^2 + 3n + 1

如果有多个变量的话需要那么要将多个变量都表示出来
比如:

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

其时间复杂度就是O(n+k)

常见的递推式与复杂度

递推式	复杂度
T(n)=T(n/2)+O(1)	O(logn)
T(n)=T(n-1)+O(1)	O(n)
T(n)=T(n/2)+O(n)	O(n)
T(n)=2*T(n/2)+O(1)	O(n)
T(n)=2*T(n/2)+O(n)	O(nlogn)
T(n)=T(n-1)+O(n)	$O(n^2)$
T(n)=2*T(n-1)+O(1)	$O(2^n)$
T(n)=2*T(n-1)+O(n)	$O(2^n)$