算法
- 取 某个值或某个值的集合 作为 输入
- 产生 某个值或某个值的集合 作为 输出
将输入转化成输出的计算步骤的一个序列
按照这个定义先有问题的形式化描述：
输入：
输出：
形式化描述
举例：leetcode两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个
整数，并返回它们的数组下标。
输入：n个数的一个序列nums=<a1, a2, … , an> 和一个值target
输出：下标集合(i, j)，使得target = nums[i]+nums[j] 或者当不存在这样集合时，集合为NIL
循环不变式
- 初始化：循环的第一次迭代前(循环头的第一次测试开始之前)为True
- 保持：if 循环的某次迭代前为True，then 下次迭代前仍为True
- 终止：循环终止，不变式将提供一个有用的性质，该性质证明算法的正确性
循环不变式与数学归纳法
如果给定一系列命题，
A
s
A_s
As?,
A
s
+
1
A_{s+1}
As+1?,
A
s
+
2
A_{s+2}
As+2?,…
?
s
∈
N
\quad\forall s\in\mathbb N
?s∈N
- 基本情况：
A
s
A_s
As?已知是真的
- 归纳步：对每个
r
≥
s
r \geq s
r≥s的值，
A
r
A_r
Ar?为真时，也能推出
A
r
+
1
A_{r+1}
Ar+1?为真
- 总结：则所有命题
A
s
A_s
As?,
A
s
+
1
A_{s+1}
As+1?,
A
s
+
2
A_{s+2}
As+2?,… ,都是真的
循环不变式的分析详见排序算法章节
伪代码
为了更简洁表达算法的本质
以插入排序为例：
INSERTION-SORT(A)
for j=2 to A.length
key=A[j]
//将A[j]插入到已排序数组A[1..j-1]中
i=j-1
while i>0 and A[i]>key
A[i+1]=A[i]
i=i-1
A[i+1]=key
练习
输入：n个数的一个序列
A
A
A=<
a
1
a_1
a1?,
a
2
a_2
a2?,…,
a
n
a_n
an?>和一个值
v
v
v
输出：下标i使得
v
v
v =
A
[
i
]
A[i]
A[i]或者当
v
v
v 不在
A
A
A中出现时，
v
v
v为特殊值
N
I
L
NIL
NIL
(1):伪代码
(2):循环不变式
两个n位二进制整数相加 ，两个整数分别存储在两个n元数组
A
A
A和
B
B
B中，这两个整数的和应按二进制形式存储在一个
(
n
+
1
)
(n+1)
(n+1)元数组
C
C
C中。
(1):形式化描述
(2):伪代码
|