😝
目录
一、什么是算法
二、如何评判一个算法的好坏
三、大O表示法
四、常见的复杂度
一、什么是算法
使用不同算法，解决同一个问题，效率可能相差非常大
需求: 求第n个斐波那契数
分析：
斐波那契数列的排列是：1，1，2，3，5，8，13，21，34，55，89，144……
这个数列从第三项开始，每一项都等于前两项之和。
package com.hp;
import com.hp.Times.Task;
public class Main {
public static void main(String[] args) {
int n = 40;
Times.check("fib", new Task() {
@Override
public void execute() {
System.out.println(fib(n));
}
});
Times.check("fib1", new Task() {
@Override
public void execute() {
System.out.println(fib1(n));
}
});
Times.check("fib2", new Task() {
@Override
public void execute() {
System.out.println(fib1(n));
}
});
Times.check("fib3", new Task() {
@Override
public void execute() {
System.out.println(fib1(n));
}
});
Times.check("fib4", new Task() {
@Override
public void execute() {
System.out.println(fib1(n));
}
});
}
//递归形式 速度慢 O(2^n)
public static int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib( n - 2 );
}
/**
* 0 1 2 3 4 5 6 i
* 0 1 1 2 3 5 8 13 ....
* 求第2个波那契数 假设 i = 3 的时候 要加2次 0 + 1 = 1 1 + 1 = 2
* 求第3个波那契数 假设 i = 4 的时候 要加3次 0 + 1 = 1 1 + 1 = 2 1 + 2 = 3
*/
//计算速度快 O(n)
public static int fib1(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; //加完之后的结果要给下一次的second
first = second;
second = sum;
}
return second;
}
//计算速度快 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++) {
second += first;
first = second - first;
}
return second;
}
//计算速度快 O(n)
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;
}
//线性代数解法 计算速度最快 O(1)
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);
}
图片.png
如何评判一个算法的好坏
对同一组输入的执行处理时间（事后统计法）eg:求第n个斐波那契数
缺点：
1.执行时间严重依赖于硬件以及运行时各种不确定的环境因素（比如：CPU）
2.必须编写相应的测算代码
3.测试数据的选择比较难保证公正性
一般从以下维度来评估算法的优劣:
1.正确性、可读性、健壮性
2.时间复杂度:估算程序指令的执行次数（执行时间）
3.空间复杂度:估算所需占用的存储空间
三、大O表示法
一般用大O表示法来描述复杂度，它表示的是数据规模 n 对应的复杂度
//如何估算时间复杂度 学会估算时间复杂度 O表示估算的意思
public static void test1(int n) {
// 1
if (n > 10) {
System.out.println("n > 10");
} else if (n > 5) { // 2
System.out.println("n > 5");
} else {
System.out.println("n <= 5");
}
// 1 + 4 + 4 + 4 = 13
//i = 0 执行次数:1次
// i++ 执行次数:4次
// i < 4 执行次数:4次
//打印 执行次数:4次
//O(1)
for (int i = 0; i < 4; i++) {
System.out.println("test");
}
}
public static void test2(int n) {
// O(n)
// 1 + 3n
//i = 0 执行次数:1次
// i++ 执行次数:n次
// i < n 执行次数:n次
//打印 执行次数:n次
for (int i = 0; i < n; i++) {
System.out.println("test");
}
}
public static void test3(int n) {
// 1 + 2n + n * (1 + 3n)
// 1 + 2n + n + 3n^2
// 3n^2 + 3n + 1
// O(n^2)
// O(n)
for (int i = 0; i < n; i++) {
//外层for 执行n次
//内存for 执行（1+3n）次
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
public static void test4(int n) {
// 1 + 2n + n * (1 + 45)
// 1 + 2n + 46n
// 48n + 1
// O(n)
for (int i = 0; i < n; i++) {
for (int j = 0; j < 15; j++) {
System.out.println("test");
}
}
}
public static void test5(int n) {
// 8 = 2^3 则4 2 1
// 16 = 2^4
// 3 = log2(8)
// 4 = log2(16)
// 执行次数 = log2(n)
// O(logn)
while ((n = n / 2) > 0) {
System.out.println("test");
}
}
public static void test6(int n) {
// log5(n)
// O(logn)
while ((n = n / 5) > 0) {
System.out.println("test");
}
}
public static void test7(int n) {
// 1 + 2*log2(n) + log2(n) * (1 + 3n)
// 1 + 3*log2(n) + 2 * nlog2(n)
// O(nlogn)
for (int i = 1; i < n; i = i * 2) {
// 1 + 3n
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
忽略常数、系数、低阶
9 >> O(1)
2n+3 >> O(n)
n^2+2^n+6 >>O(n^2)
4n^3 + 3n^2 + 22n+100 >> O(n^3)
注意:大O表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率
对数阶的细节
- 对数阶一般省略底数，eg:log2n = log29 ∗ log9n
所以 log2n 、log9n 统称为 logn
四、常见的复杂度
常见的复杂度
性能从高到低
数据规模较小时性能图
数据规模较大时性能图
fib函数的时间复杂度分析
首先我们再次回顾一下代码
//递归形式 2^n
public static int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib( n - 2 );
}
假设n=5
用大O表示法
