算法

Algorithm

算法

概述

.解决问题的方法和步骤

.算法是一个过程：由一些明确的规则组成

.通常和特定的数据结构联系在一起

.结构化算法

算法 + 数据结构 = 程序

- Pascal语言发明者沃思Wirth

要素

1.操作

2.控制结构

操作
分类	说明
算术运算	+ - * /
逻辑运算	&& \|\| !
关系运算	< >= ≤
传送运算	输入、输出、赋值

控制结构
分类	说明
顺序	按照先后顺序依次执行最简单、最常用
条件	根据可能出现的情况进行分析和处理 IF-ELSE SWITCH-CASE
循环	当型：先判定后执行 WHILE-DO 直到型：先执行后判定，至少执行1次 DO-WHILE 按指定次数循环 FOR

while-do [JavaScript]

let i = 0
while (i < 10) {
  console.log(i)
  i++
}

do-while [JavaScript]

let i = 0
do {
  console.log(i);
  i++
} while (i < 10);

For - 递增型 [JavaScript]

for (let i = 0; i < 10; i++) {
  console.log(i);
}

For - 递减型 [JavaScript]

for (let i = 10; i > 0; i--) {
  console.log(i);
}

特征

唐纳德.克努斯Donald E.Knuth归纳为：

有穷性 Finiteness

算法的执行步数是有限的

可以终止

不能出现死循环

确定性 Definiteness

相同的输入只能得到相同的输出

不能有二义性

可行性 Effectiveness

可以执行*

输入 Input

可以有1个输入或多个输入，也可以没有输入

输出 Output

有1个或多个输出

分类

1.数值型算法

算术运算占主导

2.非数值型算法

逻辑运算占主导

算法 vs 程序

.算法独立于程序

.程序不一定无穷

.程序的指令是机器可执行的

.程序由算法和相应的数据结构组成

.程序侧重于实现

表示

自然语言

优点：熟悉、方便、易理解

缺点：有歧义、表达繁琐冗长、计算机不能处理

流程图 flowchart

采用框图、线条和文字描述算法

形象、直观

常用工具：ProcessOn、Draw io 、ChatGPT

流程图基本组成
分类	说明
终端 terminal	程序的开始和结束；圆角矩形
输入 Input/输出 Output	承接输入，展示输出；平行四边形
过程 Process	内部计算操作；矩形
决策 Decision	判断True/False；菱形
连接	圆形
控制流 Control Flow	展现流程的方向；带方向的箭头

伪代码 pseudocode

使用介于自然语言和计算机语言之间符号和文字来描述算法

不拘泥于语法结构，比较灵活

基本规则

begin表示开始；end表示结束

input表示输入；output表示输出；print表示打印

在伪代码中，每一条指令占一行

指令后不跟任何符号

用缩进表示程序的逻辑结构

赋值语句使用 ←

注释用双斜杠//

数组：数组名[下标, 上标]；数组项：数组名[序号]

其它：...

基本结构

算法名称

指令序列

输入/输出

分支选择

赋值

循环

算法结束

优点：结构性强、容易书写和理解

缺点：计算机不能识别、执行

输入3个数，打印输出最大的数

BEGIN
  MAX
  INPUT A
  INPUT B
  INPUT C
  IF A > B THEN
    MAX ← A
  ELSE
    MAX ← B
  IF C > MAC THEN
    MAX ← C
  PRINT MAX
END

计算机语言

可以被计算机执行

必须严格遵守语法规则

1. 低级语言

机器语言、汇编语言

2. 高级语言

VBScript、c/c++、JavaScript、java、python

基本方法

枚举法 enumerate

也叫穷举法或试凑法

根据部分条件确定大致范围，逐一验证，直到所有可能情况都都验证完毕

时间消耗较长，好在现在计算机的运行速度足够块

经典案例：百钱买百鸡、五家共井、谁做的好事、冒泡排序、选择排序

百钱买百鸡 - “鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？” - 数学家张丘建·《算经》

设鸡翁x只，鸡母y只，鸡雏z只，根据条件有：

5x + 3y + z/3 = 100

x + y + z = 100

消去z，得：7x + 4y = 100

变形：4*(7x/4 + y) = 100，7x应该是4的倍数，也就是说，x是4的倍数

设 x = 4t

则 y = 25 - 7t

z = 75 + 3t

∴ 鸡翁每增四，鸡母每减七，鸡雏每益三

可能方案
t	鸡翁	鸡母	鸡雏
0	0	25	75
1	4	18	78
2	8	11	81
3	12	4	84

去掉第1组数据，后面3组都是购买方案

五家共井，甲二绠不足，如乙一绠；乙三绠不足，如丙一绠；丙四绠不足，如丁一绠；丁五绠不足，如戊一绠；戊六绠不足，如甲一绠，皆及。

《九章算数》 - 张苍、耿寿昌

迭代法 iterator

又称递推法、递归法

利用问题本身某种递推关系求解问题的一种方法

不断用旧值去推导新值，将复杂过程简化为一个个重复的基本过程

猴子吃桃。猴子有若干个桃子。第一天吃了一半多一个；第二天吃了剩下的一半多一个；以后每天都吃剩下的一半多一个；第七天只吃了一个。问猴子共有多少桃子

从后往前推

第七天只有1个桃子，是第六天剩下的一半少一个。所以 +1再乘2就是第6天的桃子个数：(1 + 1)*2 = 4

第六天桃子个数的是第五天的一半少1。所以第五天的桃子个数：(4 + 1)*2 = 10

同理，第四天的桃子个数：(10 + 1)*2 = 22

同理，第三天的桃子个数：(22 + 1)*2 = 46

同理，第二天的桃子个数：(46 + 1)*2 = 94

同理，第一天的桃子个数：(94 + 1)*2 = 190

斐波那契数列 Fibonacci sequence

F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)，（n ≥ 2，n ∈ N*）

求斐波那契数列F(5)

F(0)	1
F(1)	1
F(2) = F(1) + F(0)	1 + 1 = 2
F(3) = F(2) + F(1)	2 + 1 = 3
F(4) = F(3) + F(2)	3 + 2 = 5
F(5) = F(4) + F(3)	5 + 3 = 8

阶层 Factorial

fac(n) = n*fac(n - 1)，（n ≥ 2，n ∈ N*）

fac(n) = n*(n - 1)*(n-2)*...*2*1

fac(0) = 1

求阶层5!

5! = 5*4*3*2*1 = 120；代码实现过程如下

0! = 1

1! = 1*0! = 1

2! = 2*1! = 2

3! = 3*2! = 3* 2= 6

4! = 4*3! = 4*6 = 24

5! = 5*4! = 5*24 = 120

n的阶层

function fac(n) {
if (n == 0) {
  return 1
} else {
  return n * fac(n - 1)
}
}

排序 sort

冒泡排序: 不断两两比较，把：小的数据浮上来|放到序列前面；大的数据沉下去|放到序列后面; 视频解析 bubbleSort; 更多内容，请访问冒泡排序; 冒泡排序
选择排序: 从无序序列中把小的数据项选择出来，放到有序序列的最后面; 视频解析 selectSort; 更多内容，请访问选择排序

查找 search

顺序查找: 从序列的一端开始，依次将记录的关键字和给定值进行比较：如果相等，查找成功；若查找整个表后，没有匹配的记录，查找失败; 最少查找次数1；最多查找次数n；平均查找次数|比较长度 ASL = (n + 1)/2; 适用于数据量小的情况；当序列特别多时，不适合顺序查找; 时间复杂度 O(n); 更多内容，请访问顺序查找
二分查找法: 将序列看作一个区间，用low、high，mid = (low + high)/2 标识区间的下界、上界和中间位置；mid取整除结果; 如果给定值小于中间记录值，则在前半段继续查找，high = mid - 1，low不变; 如果给定值大于中间记录值，则在后半段继续查找，low = mid + 1，high不变; 如果比较到最后，low > high ，查找结束; 适合|必须有序表; 查找范围每次都缩小一半，所以查找效率高; 时间复杂度 O(lgn); 更多内容，请访问二分查找法

练习 drill

对n个元素进行排序，使用冒泡法进行排序时，共需要比较（）次。

n(n - 1)

n(n + 1)

n(n - 1)/2

n(n + 1)/2

n = 1，比较次数为0；排除B、D

n = 2，比较1次，排除A

从n个元素中顺序查找一个元素，最多的查找次数是（）。

n/2

lgn

从n个元素中顺序查找一个元素，平均查找次数是（）。

(n - 1)/2

(n + 1)/2

n(n - 1)/2

n(n + 1)/2

用选择排序法对数据7、6、3、9、2从大到小排序，共需经过（）数据对调。

选择最小的放前面

72交换：2放前面，2 6 3 9 7

63交换：3放前面，2 3 6 9 7

97交换：7放前面，2 3 6 7 9

用折半查找法从数3、6、7、10、12、16、25、30、75中查找数据10的最少查找次数是（）。

第1次：(0 + 8)/2 = 4, 12 > 10, 前半段

第2次：(0 + 3)/2 = 1, 6 < 10, 后半段

第3次：(2 + 3)/2 = 2, 7 < 10, 后半段

第4次：(3 + 3)/2 = 3, 10 = 10,查找成功

复杂度

衡量算法的效率：执行的时间快慢|时间复杂度和消耗的内存空间|空间复杂度; 更多的关注是时间快慢，即：时间复杂度; 两个方面是互相制约的；很多情况下，需要"以时间换空间"或"以空间换时间"
时间复杂度 time complexity: 算法是运行时间; 除了和算法的优劣有关系外，还和计算机硬件、编程语言和编译器有关; 很难精确统计执行时间; 关注：输入的数据量和时间的关系; 更多信息，请访问绪论
空间复杂度 space complexity