如何评价一个算法的好坏
- 正确性：算法执行结果正确
- 可读性：算法简单可读
- 健壮性：算法对不合理的输入的容错能力
- 时间复杂度：估算程序指令的执行次数（执行时间）
- 空间复杂度：估算程序所占用的内存空间
时间复杂度
时间复杂度计算
package com.shawntime.algorithms.times;
/**
* 时间复杂度计算：假设一个分号结尾为一次执行指令
*/
public class TimeComplexityTest {
/**
*
* 执行次数：14
* 时间复杂度：O(1)
*/
public static void test1(int n) {
// System.out.println : 1
if (n > 10) {
System.out.println("n > 10");
} else if (n > 5) {
System.out.println("n > 5");
} else {
System.out.println("n <= 5");
}
/**
* i = 0 : 1
* i < 4 : 4
* i++ : 4
* System.out.println : 4
*/
for (int i = 0; i < 4; i++) {
System.out.println("test");
}
}
/**
* 执行次数：3n + 1
* 时间复杂度：O(n)
*/
public static void test2(int n) {
/**
* i = 0 : 1
* i < n : n
* i++ : n
* System.out.println : n
*/
for (int i = 0; i < n; i++) {
System.out.println("test");
}
}
/**
* 执行次数： 2n + 1 + 3n^2 + n = 3n^2 + 3n + 1
* 时间复杂度：O(n^2)
*/
public static void test3(int n) {
/**
* i = 0 : 1
* i < n : n
* i++ : n
* 2n + 1
*/
for (int i = 0; i < n; i++) {
/**
* j = 0 : 1
* j < n : n
* j++ : n
* System.out.println : n
* n * (3n + 1) = 3n^2 + n
*/
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
/**
* 执行次数：2n + 1 + 46n = 48n + 1
* 时间复杂度：O(n)
*/
public static void test4(int n) {
// 1 + 2n + n * (1 + 45)
// 1 + 2n + 46n
// 48n + 1
// O(n)
/**
* i = 0 : 1
* i < n : n
* i++ : n
* 2n + 1
*/
for (int i = 0; i < n; i++) {
/**
* j = 0 : 1
* j < 15 : 15
* j++ : 15
* System.out.println : 15
* n * (15 * 3 + 1) = 46n
*/
for (int j = 0; j < 15; j++) {
System.out.println("test");
}
}
}
/**
* 执行次数 = log2(n)
* 时间复杂度：O(logn)
*/
public static void test5(int n) {
// 8 = 2^3
// 16 = 2^4
// 3 = log2(8)
// 4 = log2(16)
while ((n = n / 2) > 0) {
System.out.println("test");
}
}
/**
* 执行次数 : log5(n)
* 时间复杂度：O(logn)
*/
public static void test6(int n) {
while ((n = n / 5) > 0) {
System.out.println("test");
}
}
/**
* 执行次数： 1 + 2 * log(n) + log(n) * (3n + 1) = 1 + 3log(n) + 3nlog(n)
* 时间复杂度：O(nlogn)
*/
public static void test7(int n) {
/**
* i = 1 : 1
* i < n : log(n)
* i = i * 2 : log(n)
* 1 + 2 * log(n)
*/
for (int i = 1; i < n; i = i * 2) {
/**
* j = 0 : 1
* j < n : n
* j++ : n
* System.out.println : n
* log(n) * (3n + 1)
*/
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
/**
* 执行次数：3n + 1
* 时间复杂度： O(n)
*/
public static void test8(int n) {
int a = 10;
int b = 20;
int c = a + b;
int[] array = new int[n];
/**
* i = 0 ：1
* i < array.length : n
* i++ : n
* System.out.println : n
* 3n + 1
*/
for (int i = 0; i < array.length; i++) {
System.out.println(array[i] + c);
}
}
/**
* 执行次数：3n + 1 + 3m + 1 = 3(m + n) + 2
* O(m + n)
*/
public static void test9(int n, int m) {
/**
* i = 0 : 1
* i < n : n
* ++i : n
* System.out.println : n
* 3n + 1
*/
for (int i = 0; i < n; ++i) {
System.out.println("i:" + i);
}
/**
* i = 0 : 1
* i < m : m
* ++i : m
* System.out.println : m
* 3m + 1
*/
for (int i = 0; i < m; ++i) {
System.out.println("m:" + i);
}
}
}
大O表示法
一般用大O表示法来描述复杂度，它表示的是数据规模n对应的复杂度，大O表示法是一种粗略的估算分析模型，能帮助我们短时间内了解算法的复杂度
大O表示法使用规则：忽略常数、系数、阶数
- 9 ------------- O(1)
- 2n + 3 ------------- O(n)
- n^2 + 2n + 6 ------------- O(n^2)
- 4n^3 + 3n^2 + 2n + 1000 ------------- O(n^3)
- log2(n) ------------- O(log(n))
- log9(n) ------------- O(log(n)) 【log2(n) = log2(9) * log9(n)】
常见的复杂度
- 常数阶：O(1) 例：12、18、24
- 线性阶：O(n) 例：n、2n、2n+10
- 平方阶：O(n^2) 例：2 * n^2 + 4n + 10
- 对数阶：O(logn) 例：4log2(n) + 10
- nlogn阶：O(nlogn) 例：2nlog3(n) + 2n + 1
- 立方阶：O(n^3) 例：4n^3 + 2n^2 + 5n + 1
- 指数阶：O(2^n) 例：2^n
复杂度效率
O(1) > O(logn) > O(n) > O(nlogn) > O(n^2) > O(n^3) > O(2^n) > O(n!) > O(n^n)
空间复杂度
空间复杂度是算法在运行过程中临时占用存储空间的一个量度，同时反映的是一个趋势
- O(1)：表示算法执行所需要的临时空间不会随着n的增加而变化
- O(n)：int[] m = new int[n]; 随着n变大，申请的内存空间随之变大
斐波那契数列函数的复杂度分析
public static int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
image-20210706211926259
n = 0 ：执行次数：1 2^0
n = 1 ：执行次数：1 2^0
n = 2 ：执行次数：3 2^1 + 2^0
n = 3 ：执行次数：5 2^2 + 2^1 + 2^0
n = 4 ：执行次数：9 2^3 + 2^2 + 2^1 + 2^0
n = 5 ：执行次数：15 2^4 + 2^3 + 2^2 + 2^1 + 2^0
f(n) = 2^(n-1) -1 = 0.5 * 2^5 - 1 = O(2^n)
算法优化方向
- 用尽量少的存储空间
- 用尽量少的执行时间
- 根据实际情况，采取空间换时间，或时间换空间
