计算机算法笔记

分析算法和问题：原理和例子

算法可解的

说一个问题是算法可解的，意味着：

可以编写一个计算机程序，在足够的时间和空间内，这个程序可以为任意输入处理出一个正确的结果。

算法

20世纪30年代，计算机出现之前，数学家们已经在积极地定义和研究算法的概念。

算法被解释成：

一套清楚的简单指令，按照这套指令可以解决某个问题和计算某个函数。

停机问题

能否判断一个任意给出的算法（或计算机程序）在给定输入的情况下是否最终停止。

阿兰·图灵建立了一个重要的否定结论是，这个问题不能用计算机程序解决。

这个问题的意思是说，我能不能用一个程序来判断任意的一个程序在某个特定的输入下是不是会终止。

这个问题的意义在哪里…

继续

实际应用中大量问题都是可解决的，但是我们可能没有足够的时间或者存储空间，因此有了计算机科学中的一个分支计算复杂性。

我们可以使用复杂性的公理来证明任意一个复杂问题的存在，以及问题有没有最好的程序。

几个很有用的算法

分而治之(divide and conquer)
贪婪算法(greedy algorithms)
深度优先搜索(depth first search)
动态编程(dynamic programming)

一些约定

函数的完全类型特征指返回类型和参数类型的组合，也叫原型
过程是一个可以取名字、可以被调用的计算步骤序列（带参数）
函数是一个可以向调用者返回值的过程
私有数据的维护叫封装或信息隐藏
重载指一个方法有多个带不同参数的定义，但有相同的返回值
覆盖指子类覆盖父类的方法

组织者类

指一种只是为了将多个实例域组合在一起的简单的类。

通常实现为内部类。

组织者类中只有一个copy()方法

数学知识

集合的定义方法

集合指一堆不同的元素（通常有同样的类型），集合中的元素没有固定的顺序

列举法
描述法

两种方式都在一对大括号中，如下

$$
S_1=\{a, b, c\}, S_2=\{x\vert x是2的整数次幂\}, S_3=\{1,\dots,n\}
$$

集合的基指集合中的元素的数量，记为$\vert S\vert$

序列

以特定顺序组合的一组元素称为序列，此外，序列中的元素可以是重复的。

通常像这么表示：

$$
(a,b,c),(b,c,a),(1,\dots,n)
$$

元组

元组则指一个有不同类别元素的有限序列（也可以是相同的）

两个集合$S$和$T$的叉积，是一个对(二元组)的集合，每个对的第一个元素来自$S$，第二个元素来自$T$:

$$
S\times T=\{(x,y)\vert x\in S,y\in T\}
$$

元组可以根据数量分为二元组，三元组，四元组以及更多的n元组（一个大概是不行的，但我不确定）

集合的叉积迭代指类似如下的事情：

$$
S\times T\times U=\{(x,y,z)\vert x\in S,y\in T,z\in U\}
$$

一些结论或者关系或者定义

集合之间的关系： $\subseteq$, $\subset$, $\supseteq$, $\supset$以及其他更多的关系

如果有限序列的所有元素都不同，那么我们称该序列是由同样的元素构成的有限集合的一个排列。

一个有$n$个元素的集合有$n!$个排列，有$2^n$个子集(包括自身和空集)，有$c_n^k$个基为$k$的子集。

$c_n^k$又称为二项式系数,计算如下：

$$
c_n^k=\frac{n!}{(n-k)!k!}
$$

关系和函数

关系是叉积的一个简单子集，可以是有限的/无限的/空集/叉积本身。

如实数上的小于关系：

$$
\{(x,y)\vert x\in R,y\in R,x\lt y\}
$$

假设有关系$R$，符号$xRy$表示$(x,y)\in R$

关系的一些属性：

自反性

对于所有$x\in S$，有$(x,x)\in R$

对称性

$(x,y)\in R$，则$(y,x)\in R$

反对称性

$(x,y)\in R$，则$(y,x)\not\in R$

传递性

$(x,y)\in R$且$(y,z)in R$，则$(x,z)\in R$

全等

全等关系指一个满足自反、对称和可传递的关系，记做$\equiv$(又称为等价关系)

等价关系可以将底层集合划分为一组不相交的子集（也叫等价类），其中每个子集都是等价的。

如果$R$是$S$的一个等价关系，我们称$R$等价于$S$

许多涉及二元关系的问题可以转换为一个图上的问题，如我们可能会在后面遇到形如“任务x必须在任务y完成之后才可以开始，有固定的人来完成固定的任务，如何安排在最短时间内完成”这样的问题。

代数和微积分工具

Floor和Ceiling

$\lfloor{x}\rfloor$表示小于或等于$x$的最大整数，$\lceil{x}\rceil$表示大于或等于$x$的最小整数。

对数的注意事项

（一大部分的数学知识…我应该整理一些我比较不熟悉的）

$x^{\log_by}=y^{\log_bx}$
对数函数的复合： $\lg\lg(x)=\lg(\lg(x))=\lg^{(2)}(x)$

如果$n$不是$2$的幂，则有一个整数$k$使得$2^k\lt{n}\lt2^{k+1}$

此时$\lfloor{\lg{n}}\rfloor=k$且$\lceil{\lg{n}}\rceil=k+1$

然后还有两个不等式：

$n\le2{\lceil{n}\rceil}\le{2n}$
$\frac{n}{2}\le2{\lfloor{n}\rfloor}\le{n}$

概率

基本事件：假设在给定的状况下，一个事件或试验有一个或$k$个结果，这些结果叫基本事件，记为$s_1,s_2,s_3,\dots,s_k$
所有基本事件的集合叫事件空间，以$U$标记。

级数

单调递增函数和凸函数

积分

逻辑元素

分析算法和问题

分析一个算法的目的是要改进他，为在解决一个问题中到底选择哪一个方法提供依据。

我们使用下面的标准：

正确性
所做工作的量（时间复杂度）
使用空间的量
简单，清晰
最优性

后面会介绍建立问题最低边界复杂性的技术。

正确性

建立算法的正确性有三步：

对“正确”有一个清晰的概念
需要一个清晰的命题来描述期望有效输入的特性（前提）
需要处理每一个输出的结果（后置条件）

在输入前提条件满足，算法结束之后后置条件也正确的话，我们尝试证明输入输出关系的命题。

这一段有点乱，后面回来整理吧。

算法有两个方面，一是要解决的问题，二是解决问题所需要的指令序列。

什么是循环不变式(loop invariants)？

所做工作的量

不是简单地比较执行的时间，时间会随着不同的计算机而变化，但我们可以用执行的指令数或者语句的数量来代替执行时间。

一个简单的算法可能由一堆初始化构造和循环组成，此时我们可以用循环体执行的次数来衡量工作量。

在许多时候，为了分析一个算法，我们可以隔离出一种解决所研究问题的基本操作。

比如在如下问题中可以有这样的基本操作：

问题	操作
在一个数组中查找x	比较x和数组中的元素
两个实数矩阵相乘	两个实数做乘法（或者乘法和加法）
数组排序	比较数组的两个元素
遍历二叉树	便历边
任一迭代过程	过程调用

选定了基本操作之后，我们就可以粗略地估计执行基本操作的数目。

算法所做工作的度量也可以用一个算法的复杂性来代替。

平均和最坏分析

我们知道工作量的大小不能用一个简单的数值来描述，对于不同的输入算法执行的步数也可能不同。

工作量依赖于输入量的大小，也依赖于具体输入的值。

我们可以根据工作量依赖于输入量的大小指出一个输入规模的度量：

问题	输入的规模
在名字数组中查找 x	数组中名字的个数
两个矩阵乘法	矩阵的维数
遍历二叉树	树节点的数量
解系统的线性方程	等式的数量，或未知数的数量，或者两者
一个关于图的问题	图节点的数量，或边的数量，或者两者

我们经常使用最坏情况复杂性来描述算法的行为。

定义如下：

令$D_n$是所考虑问题的规模为$n$的输入集合，$I$是$D_n$的一个元素。令$t(I)$是对于输入$I$要执行的基本操作的数量。我们定义函数$W$

$$
W(n)=\max\{t(I)\vert I\in D_n\}
$$

函数$W(n)$称为算法的最坏复杂性，是对于规模为$n$的输入所要做的基本操作的最大数量。
除非特别指出，当我们说一个算法的工作量时，都是指最坏情况时的工作量。
当然有时候计算平均复杂度或者带权平均复杂度更有用。

平均复杂性的定义如下：

$$
A(n)=\sum\limits_{I\in D_n}P_r(I)t(I)
$$

$P_r(I)$通过一些假设或者先验知识来获得。

下面是一个展示平均和最坏分析的例子：

这是一个最坏情况的冒泡排序，我们比较并交换了$10$次数组中的元素。

如果是最好的情况（已排序），我们只需要比较$4$次并且不做任何的交换就可以了。

我们对于输入$n$，可以得出冒泡排序中最坏情况需要比较和交换$1+2+\dots+(n-1)$次，也就是$\frac{n(n-1)}{2}$次。

看一个书上的例子，查找某个数在数组中的位置：

int seqSearch(int[] E, int n, int K) {
    int ans, index;
    ans = -1;
    for(index = 0; index < n; ++index) {
        if (K == E[index]) {
            ans = index;
            break;
        }
    }
    return ans;
}

我们定义一下基本操作为比较$x$和数组的元素。

最坏分析： $W(n)=n$，也就是把所有的元素都比较以便才找到或者没找到对应的位置。

我们在假定数组中的元素各不相同下分析一下平均情况，记事件$K$在数组$E$中为$succ$,不在记为$fail$。

当$K$在$E$中时，令$t(I)$为输入$I$时的比较次数，我们有:

$$
\begin{split}
A_{succ}(n)&=\sum_{i=0}^{n-1}P_r(I_i\vert succ)t(I_i) \\
&=\sum_{i=0}^{n-1}(\frac{1}{n})(i+1) \\
&=\frac{n+1}{2}
\end{split}
$$

而$K$不在$E$中时我们有：

$$
A_{fail}(n)=n
$$

进一步：

$$
A(n)=P_r(succ)A_{succ}(n)+P_r(fail)A_{fail}(n)=n(1-\frac{1}{2}q)+\frac{1}{2}q
$$

其中$q$为$K$在$E$中的概率。

再看一个