算法导论笔记
读算法导论
记录一下读算法导论的过程
1.算法
如果问我什么是算法（思考中）
利用数据结构，考虑时间以及空间效率，高效的解决一系列数学或是计算机问题的方法
而书中： 算法（algorithm） 就是任何良定义的计算过程，该过程取某个值或值的集合作为输出并产生某个值或值的集合作为输出。这样算法就是把输入转换成输出的计算步骤的一个序列。
- 算法解决哪些问题
书中举例了DNA序列的储存以及分析（30亿个化学基对的序列）
互联网搜索引擎的索引以及数据处理
电商的公私钥以及数字签名
......
其中还提到了NP完全问题（Non-deterministic Polynomial）世界七大数学难题
所有可以在多项式时间内求解的判定问题构成P类问题
所有的非确定性多项式时间可解的判定问题构成NP类问题（无法直接计算得到的，只能通过间接的“猜算”来得到结果。这就是非确定性问题，比如找大质数，只能一个个试）
NP中的某些问题的复杂性与整个类的复杂性相关联.这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的.这些问题被称为NP-完全问题(NPC问题)
现在人们想要证明 NP = P 或是 NP != P
傅里叶变换
傅立叶变换，表示能将满足一定条件的某个函数表示成三角函数（正弦和/或余弦函数）或者它们的积分的线性组合
书中提到了（离散傅里叶变换把时域转变为频域，数据压缩，采样信号中各种频率强度）
然后我就去查了一下（还是知乎大佬牛逼）把这个抽象问题说明了
看了点知乎相关之后，再去看了下李永乐老师的数学，大致知道了傅里叶变换的应用场景（在视频处理和音频处理上，甚至从事物最本质的角度上，傅里叶变换说明了信号的波粒性质）甚至人的大脑对声波的区分从本质上来说就是一种傅里叶变换的体现
这里大致记录一下我对傅里叶变换的一些粗浅的理解
首先从二维平面图到数字的变换很简单
图上的点A（2，1），和点B（1，2）很容易就能绘制出来
然后又有一个标准正交基的概念
(ϵi,ϵj)=δij 假如i = j 则 δij = 1 ， i 不等于j 则δij = 0
然后是傅里叶级数说明了任何周期函数都可以用正弦函数和余弦函数构成的无穷级数来表示
这样一个周期函数可以在频域空间分解成多个正余弦函数
然后通过欧拉公式 cosX + i sinX = e ix 然而 x = w * t 角度 = 频率 * 时间
傅里叶变换：
a33ju-3stzm.png
所以傅里叶变换里的e-iwt 就代表的顺时针旋转的一个正交基的组合
傅里叶逆变换：
aj1m8-43oh6.png
以上就有点偏题了，1.2章就开始介绍算法了：
插入排序： t = C1 * n ^ 2
归并排序： t = c2 * n * lgn
插入排序就是新建出一个数组，每次提取旧数组中的一个数，加入新数组的同时并保证有序
而这种情况下如果本身数组是逆序，等于是需要 1 + 2 + 3 + ... + n - 1 = n(1 + n - 1) / 2 = 1/2 * n ^ 2
就是之前的 C1 * n ^ 2
由此则出现了希尔排序（Shell排序） 最糟糕的情况下 希尔排序也能实现 t = n^(3/2) 的速度
而归并排序的排序速度仅次于快排，有二路归并，多路归并。
练习1.2
假设我们正比较插入排序与并轨排序在相同机器上的实现。对规模为n的输入，插入排序运行8n^2步，而归并排序运行64nlgn布，问对哪些n值，插入排序优于归并排序？
求解 8 * n ^ 2 < 64 * n * lgn => n < 8 lgn 通过换底公式 In2 = 0.3， 则 n < 8 * log10 (n) / 0.3
=> n < 26.666 * log10 (n) 然后我通过计算器得到了 n = 43 时 26.666 * log10 (n) 大约是 43.5591
n = 44时 26.666 * log10 (n) 大约是 43.8254 所以n应该是从1到43的正整数 n 属于 N* 且 [1, 43]
n的最小值为何值时，运行时间为100n2的一个算法在相同机器上快于运行时间为2n的另一个而算法
求解 100n^2 < 2 ^ n 由于n是N* 且 n = 3 时 n ^ 2 > 2 ^ n 且 n = 5时 100 < 2 ^ 5
100 * n ^ 2 则最先尝试 n = 3 * 5 22500 < 32768 不满足
而 n = 14 19600 > 16384 可以看出 当 n 属于 N* 且 n >= 15 时满足条件
2.1 插入排序
插入排序书上有个很好的例子，就是人们在打扑克牌的时候，每次抓到一张新牌，将其加入已经整理好的手中，就是一种插入排序的体现。
循环不变式
初始化： 循环的第一次迭代之前，它为真
保持： 如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。
终止： 在循环终止时，不变式为我们提供一个有用的性质，性质有助于证明算法是正确的
这部分说明有点抽象 =。=我个人的理解是
- 算法初始化前提：一般是构建数据结构以及解决边界问题，在插入排序中，初始化就是
构建一个有序数组，数组的元素是n1，然后向数组中插入一个元素（这个插入行为，就是一种循环行为）
- 所谓的保持：就是持续调用这个循环行为，从旧数组中提取元素，并将其加入有序数组。
- 终止就是旧数组中的所有元素都已经加入到新数组中之后，这个排序操作就可以终止了。
练习：
重写过程INSERTION-SORT，使之按非升序排序。
INSERTION-SORT(B)
for j = 2 to B.length
key = B[j]
// Insert B[j] into the sorted squenec B[1..j-1]
i = j - 1
while i > 0 and B[i] < key // 冒泡排序
B[i + 1] = B[i]
i = i - 1
A[i + 1] = key
考虑一下查找问题
输入： n个数的一个序列A={a1,a2,...,an}和一个值v
输出：下标i使得v=A[i]或者当v不在A中出现时，v为特殊值NIL.
写出线性查找的伪代码，它扫描整个序列来查找v。使用一个循环不表示来证明你的算法是正确的，确保你的循环不变式满足三条必要的性质。
SEARCH(A, v)
i = 0
while i < A.length - 1
if(A[i] == v)
return i
else
i = i + 1
return NIL
考虑把两个n位二进制整数加起来的问题，这两个整数分别存储在两个n元数组A和B中。这两个整数的和应按二进制形式存储在一个（n+1）元素组C中。请给出该问题的形式化描述，并写出伪代码。
初始化：从最右一位开始，A[n] + B[n], 如果sum > 1 则C[n + 1] = 0 且 C[n] = 1
保持： A[n] + B[n] + C[n + 1], 如果 sum = 3 则C[n + 1] = 1, C[n] = 1; 如果 sum = 2 则C[n + 1] = 0 ,C[n] = 1; 如果 sum = 1或0, 则C[n + 1] = sum;
终止：n = 0
ADD-BINARY(A,B,C)
i = A.length() - 1
while(i > 0)
sum = A[i] + B[i] + C[i + 1]
if(sum < 1)
C[i + 1] = sum
else if(sum == 2)
C[i + 1] = 0
C[i] = 1
else
C[i + 1] = 1
C[i] = 1
i = i - 1
2.2 分析算法
书上提到，本书假定一种通用的单处理器计算模型———随机访问机（RAM random-access machine）来作为我们的实现技术，算法可以用计算机程序来实现。
其中
最坏情况与平均情况分析
增长量级
在不同应用场景下，有时考虑的是最坏情况（比如查看数组中是否含有某个数）
而如果以及确定了数组里有某个数，找到他的位置，则是考虑平均情况
至于增长量级，O（n2）这样的写法以及很常见了，因为相对于n2 ， n 或是常数的量级基本可以忽略不记
练习
考虑排序存储在数组A中的n个数：首先找出A中的最小元素并将其与A[1]中的元素进行交换。接着，找出A中的次最小元素，并将其与A[2]中的元素进行交换。对A中前n-1个元素按该方式继续。该算法称为选择算法（选择排序），写出其伪代码，用O记号给出选择排序的最好情况与最坏情况运行时间。
SELECTION-SORT(A)
i = 0
while(i < A.length - 1)
min = A[i]
key = i
for j = i to A.length - 1
if(min > A[j])
min = A[j]
key = j
else
continue
swap(i, key)
i++
最好最坏情况都是一样，因为这个排序方式最终的耗时是
n + (n - 1) + ... + 2 这是一个等差数列 结果就是 n *（n + 2) / 2 增长量级O（n^2）
2.3 设计算法
这里提到了分治法，分治算法的核心思想就是：算法一次或多次递归地调用其自身以解决密切相关的若干子问题。
三个步骤：
分解（把原问题分解为若干个子问题）
解决（解决子问题，递归求解各个子问题）
合并（把子问题的解合并成原问题的解）
这里就举例了二路归并排序
