什么是算法 ?
- 算法是用于解决特定问题的一系列的执行步骤
//计算a跟b的和
public static int plus(int a,int b) {
return a + b;
}
//计算 1+2+3+...n的和
public static int sum(int n) {
int result = 0;
for (int i = 0; i <= n; i++) {
result += I;
}
return result;
}
- 使用不同算法，解决同一个问题，效率可能相差非常大
例：求第n个斐波那契数（fibonacci number）
package com.njf;
import com.njf.TimeTool.Task;
public class Main {
/* 0 1 2 3 4 5 6 7...
* 0 1 1 2 3 5 8 13...
*/
//递归，例如5是第n个，5=2+3=(n-1)+(n-2)
public static int fib1 (int n) {
if (n <= 1) return n;
return fib1(n - 1) + fib1(n - 2);
}
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++) {//求第n个斐波那契数，前面要加n-1次
int sum = first + second; //第一次相加 0+1
first = second;//下一次相加，第二个数变成了第一个数
second = sum;//下一次相加，前一次相加的和变成第二个数
}
return second;
}
public static void main(String[] args) {
int n = 45;
TimeTool.check("fib1", new Task() {
public void execute() {
System.out.println(fib1(n));
}
});
TimeTool.check("fib2", new Task() {
public void execute() {
System.out.println(fib2(n));
}
});
}
}
TimeTool测试算法时间效率的工具类
package com.njf;
import java.text.SimpleDateFormat;
import java.util.Date;
public class TimeTool {
private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS");
public interface Task {
void execute();
}
public static void check(String title, Task task) {
if (task == null) return;
title = (title == null) ? "" : ("【" + title + "】");
System.out.println(title);
System.out.println("开始：" + fmt.format(new Date()));
long begin = System.currentTimeMillis();
task.execute();
long end = System.currentTimeMillis();
System.out.println("结束：" + fmt.format(new Date()));
double delta = (end - begin) / 1000.0;
System.out.println("耗时：" + delta + "秒");
System.out.println("-------------------------------------");
}
}
下面是两个算法的在n=45时候的打印结果,可以看到fib2方法比fib1方法的执行效率明显要高
fib1】
开始：16:37:25.483
1134903170
结束：16:37:30.953
耗时：5.469秒
-------------------------------------
【fib2】
开始：16:37:30.956
1134903170
结束：16:37:30.956
耗时：0.0秒
-------------------------------------
如何评判一个算法的好坏？
//计算 1+2+3+...n的和
public static int sum1(int n) {
int result = 0;
for (int i = 0; i <= n; i++) {
result += I;
}
return result;
}
//计算 1+2+3+...n的和
public static int sum2(int n) {
return (1+n) * n / 2;
}
如果单从执行效率上进行评估，可能会想到这么一种方案
1.比较不同算法对同一组输入的执处理时间
2.这种方案也叫做：事后统计法
上述方案有比较明显的缺点
1.执行时间严重依硬件以及运行时各种不确定的环境因素
2.必须编写相应的测算代码
3.测试数据的选择比较难保证公正性
一般从以下维度来评估算法的优劣
1.正确性、可读性、健壮性（对不合理输入的反应能力和处理能力）
2.时间复杂度（time complexity）：估算程序指令的执行次数（执行时间）
3.空间复杂度（space complexity）：估算所需占用的存储空间
大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)
大O表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率
对数阶的细节
◼ 对数阶一般省略底数
log2^n = log2^9 ∗ log9^n
◼ 所以 log2^n 、log9^n 统称为 logn
常见的复杂度
◼ O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
◼ 可以借助函数生成工具对比复杂度的大小
函数图像绘制工具
数据规模较小时
数据规模较大时
fib函数的时间复杂度分析
◼ 1 + 2 + 4 + 8 = 2^0 + 2^1 + 2^2 + 2^3 = 2^4 − 1 = 2^n-1 − 1 = 0.5 ∗ 2^n − 1
◼ 所以复杂度是 O(2^n)
斐波那契的线性代数解法 – 特征方程
public static int fib3(int n) {
double c = Math.sqrt(5);
return (int)((Math.pow((1 + c) / 2, n) - Math.pow((1 - c) / 2, n)) / c);
}
时间复杂度：视为 O(1)
算法的优化方向
◼ 用尽量少的存储空间
◼ 用尽量少的执行步骤（执行时间）
◼ 根据情况
空间换时间
时间换空间
多个数据规模的情况
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");
}
}
时间复杂度为O(n + k)
leetcode
◼ 一个用于练习算法的好网站
◼ 斐波那契数
网友评论