1.什么是算法？
回答：算法是用于解决特定问题的一系列操作步骤
//计算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 = 1;i <= n; i++){
result += I
}
return result
}
- 使用不同算法,解决同一个问题，的效率可能相差非常大
- 比如：求第n个斐波那契数(Fibonacci number）
ps.不知道什么叫斐波那契数的可以自行百度
2.如何判断一个算法的好坏
- 举个栗子：
同样是计算1+2+3...+n的和
有下面两种方法
public static int sum1(int n){
int result = 0;
for (int i = 1;i <= n; i++){
result += I
}
return result
}
public static int sum2(int n){
return (1 + n) * n / 2
}
明显可以只管的看出sum2 肯定比sum1 的执行效率要好，但是判断一个算法的好坏并不是靠直观的感受来判断的，它有自己的一套量化标准，我们叫算法复杂度。
单从执行效率进行评估，可能会想到那么一种方案
- 比较不同算法对同一组输入的执行处理时间
- 这种方案叫做：事后统计法
但是这种方案有比较明显的缺点
- 执行时间严重依赖硬件及运行时各种不确定的环境因素
- 必须编写相应的测算代码
- 测试数据的选择比较难保证公正性
我们一般从以下维度来评估算法的优劣
- 正确性，可读性，健壮性（对不合理的输入的反应能力和处理能力）
- 时间复杂度（time complexity）:估算程序指令的执行次数（执行时间）
- 空间复杂度（space complexity）:估算所需要占用的存储空间
复杂度的量化单位 ->大0表示法（Big 0）
- 一般用大O 表示法来描述复杂度，他表示的数据规模n对应的复杂度
举个栗子：
public static int sum(int n){
int result = 0;
for (int i = 1;i <= n; i++){
result += I
}
return result
}
函数sum 的执行指令的次数为 2 + n (我们认为一行代码的执行就是一次计算机指令的执行) 但是在算法复杂度的计算中我会将产生直接忽略掉不管这个常数是2 还是 200000。所以sum函数的时间复杂度我们用大O表示法来表示就是 O(n)
对数阶细节
- 套用换底公式可以得出
log2n = log29 * log9n
由于log29是一个很小的常数 所以在计算算法复杂度时可以认为 log2n 与log9n是相 等的。从而可以用log2n表示所有的log级别的复杂度统称为logn
常见的复杂度
常见的复杂度
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n)
可以借助第三方工具对比复杂度的大小地址:
https://zh.numberempire.com/graphingcalculator.php
复杂度变化图小数据
复杂度变化图大数据
- 最后一个用于练习算法的网站
https://leetcode.com/
https://leetcode-cn.com/
