趣学算法14天阅读｜Day2
趣学算法14天阅读｜Day2
前言
📫 作者简介：「六月暴雪飞梨花」，专注于研究Java，就职于科技型公司后端中级工程师 🔥 三连支持：如果此文还不错的话，还请 ❤️关注、👍点赞、👉收藏三连，支持一下博主~
前一篇主要介绍了为啥学习算法，算法工程师的招聘要求，以及如何学习算法、面试算法以及面试前如何刷题等。这一篇我们开始真正的算法之旅。
什么是算法？
要想了解算法，首先得知道什么是程序。
在广泛的意义上面来讲，程序是指事物发展的既有次序和脉络以及方式、方法。从计算机编码语言上来讲，程序是数字计算机的编码指令的次序。而在广泛意义上的方式方法，则可以专业性的称之为算法。那么具体怎么描述算法呢？借用百度百科的一段话，“算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制”。这样一来，是不是同我们所描述的有次序的脉络以及方式方法所吻合？
著名的瑞士计算机科学家尼古拉斯·沃斯（Niklaus Wirth）在计算机领域有一句名言：“算法 + 数据结构 = 程序”（Algorithm+Data Structures=Programs）。数据结构是程序的骨架，而算法则是程序血肉，是灵魂。
算法的特点
如何判断一段计算机指令或程序是否是一个算法，我们可以从下面几个特点来判断：
- 有穷性：可以穷举，有终点或者结束点
- 确切性：每一个步骤都有明确的定义
- 输入性：有条件（包含0到∞个参数）
- 输出项：有结果，有结论，没有输出则没有意义
- 可行性：可以分解为最基础的单元来进行步骤的操作，每个步骤都有时间周期
算法复杂度
在没有学习计算机技术之前，我们应该对复杂度并不是很陌生，因为这是统计学的一个概念，我们接触最多的莫过于样本复杂度这个概念，这些都是在统计抽样、概率选取、概率评价等等一系列从高中就开始接触，到大学深入了解的知识。那么算法复杂度又是什么呢？
算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。当了解这个之后，我们可以深入理解下，什么是时间复杂度、空间复杂度和复杂度分析等一些更深层次的概念。实际应用中，通常使用时问复杂度渐近上界 𝑂(f(0))来表示时间复杂度。
- 时间复杂度：从算法开始运行到算法执行结束所需要的时间
- 空间复杂度：执行算法所需空间大小，运行过程中占用多少存储空间
具体到示例可以参考陈老师在书中的案例。首先给我们讲述了一个故事——一盘棋的麦子，然后引出来“爆炸增量函数”。常见的时间复杂度有以下几类：
➊常数：𝑇(𝑛) = 𝑂(c)，其中c是常数。例如运行5次、20次。常数阶算法的时间复杂度通常用𝑂(1)来表示。
➋多项式：比较常用的算法。通常用𝑂(𝑛)、𝑂(𝑛²)、𝑂(𝑛³)等表示。
➌指数：运行效率最差。通常用用𝑂(3ⁿ)、𝑂(𝑛!)、𝑂(𝑛ⁿ)等表示。
➍对数⚠️：𝑇(𝑛) =𝑂((log𝑛)^k)，运行效率最高。通常用用𝑂(log𝑛)、𝑂(𝑛logⁿ)「线性对数时间」等表示。
注意⚠️：1、MacOS中，如果想要打印出来这个上角标ⁿ，这里有一个方法。首先打开“显示字符和表情”找到拉丁文，在基本拉丁字符中找到N（任意的N都可以），在最右侧找到相关字符，其中就有小角标。
2、我们在代数运算中，将对数函数分为三类：常用对数函数（10）、自然对数函数（e）、其他对数函数，而在算法导论中lgN默认都是以2为底，这个需要留意。
如何评定好算法
算法既然有那么多的概念以及那么多的种类，一千个读者就有一千个哈姆雷特，是不是都可以称之为算法，是不是都是好算法？ 带着这个问题，看了下书籍的1.2章节，你会有比较好的答案。好算法只是一个相对概念，可以评定好算法的界限可以参考以下几点：
- 正确
- 易读
- 健壮
- 高效
- 低存储
那么，如何知道算法是否好呢，根据「陈老师」罗列的他们之间的关系：
𝑂(1) < 𝑂(log𝑛) < 𝑂(𝑛) < 𝑂(𝑛log𝑛) < 𝑂(𝑛²)< 𝑂(𝑛³) < 𝑂(2ⁿ) < 𝑂(𝑛!) < 𝑂(𝑛ⁿ)指数阶增量随着x的增加而急剧增加，而对数阶增长缓慢。
案例
案例一：棋盘的麦子
这个故事背后的指数爆炸也是当今经常困扰人们的问题，人们更期望解决问题的代价是随着问题规模赠大而以一种近似多项式形式增长而非指数增长的规模。
案例二：兔子数列
数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。斐波那契数列（Fibonacci sequence），又称黄金分割数列。
在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。
「Java实现」
//①==================================
/**
* 平推方法实现
*/
public static long fibLoop(int num) {
if(num < 1 || num > 92)
return 0;
long a = 1;
long b = 1;
long temp;
for(int i = 2; i < num; i++) {
temp = a;
a = b;
b += temp;
}
return b;
}
//②==================================
/**
* 递归方法实现
* f(n) = f(n - 1) + f(n - 2)
* 最高支持 n = 92 ，否则超出 Long.MAX_VALUE
* @param num n
* @return f(n)
*/
public static long fibRec(int num) {
if(num < 1)
return 0;
if(num < 3)
return 1;
return fibRec(num - 1) + fibRec(num - 2);
}
//③==================================
static long[] l = new long[93];
static {
l[1] = 1;
}
/**
* 带有缓存的方法，比fibRec方法性能好很多
*/
public static long fibBuffRec(int num) {
if(num < 1 || num > 92)
return 0;
if(l[num] == 0)
l[num] = fibBuffRec(num - 1) + fibBuffRec(num - 2);
return l[num];
}
//④==================================
static List<BigDecimal> list = new ArrayList<BigDecimal>(93);
static {
list.add(BigDecimal.ZERO);
list.add(BigDecimal.ONE);
}
/**
* 1，2，3，4，5，6， 7 ，8
* 1，1，2，3，5，8，13，21
* 支持num超过92的超大型数字，使用了ArrayList进行缓存以提高性能
*/
public static BigDecimal fibBig(int num) {
if(num < 0)
return list.get(0);
if (list.size() <= num)
list.add(fibBig(num - 1).add(fibBig(num - 2)));
return list.get(num);
}总结
非常感谢陈老师，让一个小白了解到很多算法方面的知识。