复杂度

什么是算法

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

1
2
3
4
5
6
7
8
9
10
11
12
13
// 计算a和b的和
public static int plue(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;
}

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

  • 比如:求第 n 个斐波那契数(fibonacci number)

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

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

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

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

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

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

  • 正确性、可读性、健壮性(对不合理输入的反应能力和处理能力)
  • 时间复杂度(time complexity):估算程序指令的执行次数(执行时间)
  • 空间复杂度(space complexity):估算所需占用的存储空间
1
2
3
4
5
6
7
8
9
10
11
12
13
// 计算 1+2+3+...+n 的和
public static int sum1(int n) {
int result = 0;
for (int i = 1; i <= n; i++) {
result += i;
}
return result;
}

// 计算 1+2+3+...+n 的和
public static int sum2(int n) {
return (1 + n) * n / 2;
}

大O表示法(Big O)

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

忽略常数、系数、低阶

  • 9 >> O(1)
  • 2n + 3 >> O(n)
  • n^2 + 2n + 6 >> O(n^2)
  • 4n^3 + 3n^2 + 22n + 100 >> O(n^3)
  • 写法上,n^3 等价于 n^3

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

对数阶的细节

对数阶一般省略底数

所以 log2n 、log9n 统称为 logn

常见的复杂度

  • O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2n) < O(n!) < O(n^n)
  • 可以借助函数生成工具对比复杂度的大小
  • https://zh.numberempire.com/

数据规模较小时

数据规模较大时

fib函数的时间复杂度分析

  • 呈现的是指数级增长的趋势

fib函数的时间复杂度分析

O(2^n)

1
2
3
4
5
// O(2^n)
public static int fib1(int n) {
if (n <= 1) return n;
return fib1(n - 1) + fib1(n - 2);
}

O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// O(n)
public static int fib2(int n) {
if (n <= 1) return n;

int first = 0;
int second = 1;
for (int i = 0; i < n - 1; i++) {
int sum = first + second;
first = second;
second = sum;
}
return second;
}

public static int fib3(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
public static int fib4(int n){
double c = Math.sqrt(5);
return (int)((Math.pow((1 + c) / 2,n) - Math.pow((1 - c) / 2, n)) / c);
}

时间复杂度:视为 O(1)

算法的优化方向

用尽量少的存储空间

用尽量少的执行步骤(执行时间)
根据情况,可以

  • 空间换时间
  • 时间换空间

多个数据规模的情况

1
2
3
4
5
6
7
8
9
public static void test(int n,int k){
for (int i = 0; i < n; i++){
System.out.println("test");
}

for (int k = 0; k < n; k++){
System.out.println("test");
}
}

O(n + k)

leetcode

一个用于练习算法的好网站

  • https://leetcode.com/
  • https://leetcode-cn.com/

斐波那契数

  • https://leetcode-cn.com/problems/fibonacci-number/