第一章

1.1 计算

计算机只是我们的工具(手段),我们研究的对象是计算。

计算 = 信息处理

借助某种工具,遵照一定规则,以明确而机械的形式进行。

机器模型 = 计算机 = 信息处理工具

所谓算法,即特定计算模型下,旨在解决特定问题的指令序列

* 输入,待处理的信息(问题)
* 输出,经处理的信息(答案)
* 正确性,的确可以解决指定的问题
* 确定性,任一算法都可以描述为一个由基本操作组成的序列
* 可行性,每一基本操作都可实现,且在常数时间内完成
* 有穷性,对于任何输入,经有穷次基本操作,都可以得到输出
好算法的定义

* 正确,对于输入有正确的输出
* 健壮,对于不合法的操作,可以恢复程序的正常执行
* 可读,结构化+准确命名+注释+ ···
* 效率,速度尽可能快,存储空间尽可能少
程序 = 数据结构 + 算法

要改进或者优化某个算法,我们需要先知道这个算法的效率。

算法分析

* 正确性,算法功能与问题要求是否一致
* 成本,运行时间+所需存储空间
通常我们对一个算法的度量值的大小都取这个度量规模的最坏情况。

对于特定问题+不同算法,我们该如何判断其优劣呢?考察以下两种模型

* TM模型(图灵机)。
* RAM模型(汇编)。
我们度量的单位为CPU的执行次数,算法在必要的时候需要复位。

大 O 记号

n为问题规模。

常系数可忽略:
O(f(n))=O(c∗f(n))O(f(n))=O(c∗f(n))
低次项可忽略:O(na+nb)=O(na),a>b>0O(na+nb)=O(na),a>b>0

其他记号:

* Big Ω,最大下界。
* Big θ ,折中。
O的等级:

* 常数,O(1)
* 对数,O(logn),以2为底数
* 多项式,O(n^c)
* 线性复杂度,O(n)
* 指数复杂度,O(2^n)
算法效率从O(2^n)到O(n^c)是一个难点。通常情况下,我们想找出一个效率从指数到多项式的算法是非常难的。这是一个分水岭。

定理:2-Subset is NP-complete。解释:就目前的计算模型而言,不存在可在多项式时间内回答此问题的算法。

NP问题就是一个幂集问题,效率为O(2^n)。

算法分析

两个主要任务 = 正确性( 不变性*单调性 ) + 复杂度。

C++等高级语言的基本指令,均等效于RAM的基本指令;在渐进意义下,二者大体相当。

复杂度分析的主要方法:

* 迭代:级数求和

* 算术级数:与末项的平方同阶
* 幂方级数:比幂次高出一阶
* 几何级数:与末项同阶
* 收敛级数:常数 O(1)(某种情况下是有意义的,比如迭代的去投掷一枚硬币,直到出现正面)
* 调和级数:O(logn)
* 对数级数:O(nlogn)
* …(有一本书叫做《具体数学》)
* 递归:递归跟踪 + 递推方程
* 猜想 + 验证
迭代与递归

迭代乃人工,递归方神通。

从效率上讲,迭代效率比递归效率要来的高。我们需要学习的是从递归到迭代的一个过程。

凡治众如治寡,分数是也。

对于一个问题,分成一系列子问题。通过求解子问题进而得出这个问题的解。

减而治之与分而治之。

动态规划

第一个例子:斐波那契数列

递归版本的fib和迭代版的fib的效率相差巨大(原因重新计算已经被计算过的fib数)。
//递归版 int fib(int n){ return (2>n)? n : fib(n-1) + fib(n-2); }
很明显这是求解一个幂集问题,这段代码时间复杂度是2的n次方,空间复杂度是O(n)。

改进1:记忆版本(制表)
//迭代 int arr[] = new int[n+1]; arr[1] = 1; arr[2] = 1; for(int i=3;i<n;i++){
arr[i] = arr[i-1]+arr[i-2]; } return arr[n];
以上时间复杂度和空间复杂度都是O(n)。

改进2:动态规划(自底而上)
//迭代 int f=0,g=1; while(0<n--){ g = g+f; f = g-f; } return g;
时间复杂度是O(n),空间复杂度是O(1)。

第二个例子:LCS序列

递归版(算法步骤):
对于序列 A[0, n] 和 B[0, m] 无非三种情况

* 若 n= -1 或 m= -1,则取作空序列(“”)
* 若 A[n]= ‘X’ =B[n],则取作LCS( A[0,n), B[0,m) ) + ‘X’
* A[n] != B[n],则在 LCS( A[0,n], B[0,m)) 与 LCS( A[0,n), B[0,m]) 中取更长者 public
static String LCS(char A[],int alo,int ahi,char B[],int blo,int bhi){ //第一种情况 if
(ahi==-1||bhi==-1){ return ""; } //第二种情况 if(A[ahi]==B[bhi]){ return
LCS(A,alo,ahi-1,B,blo,bhi-1)+A[ahi]; } //第三种情况,由于这种情况将问题分成2个子问题。 else{ String
AA = LCS(A,alo,ahi-1,B,blo,bhi); String BB = LCS(A,alo,ahi,B,blo,bhi-1); return
AA.length()>BB.length()? AA : BB; } }
明显是一个幂集问题,所以时间复杂度为O(2^n),空间复杂度为O(n)。

由递归分析,我们得出一个结论,重复元素多次计算,所以我们可以改进。

迭代版(制表):

* 第一行和第一列初始化为0
* 若行和列所对应的字母相等,则table[i][j] = table[i-1][j-1]。
* table[i][j] 取 table[i-1][j] 和 table[i][j-1] 更大者 public static void main
(String[] args) {//测试数据 String A = "DATA"; String B = "NAA"; int n = A.length();
int m = B.length(); //start LCS //初始化 int table[][] = new int[n+1][m+1]; for(int
i=0;i<n;i++){ table[i][0] = 0; } for(int j=0;j<m;j++){ table[0][j] = 0; } //迭代
for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){
//第二种情况,由于字符串是从0开始,而表格是从1开始,所以对于的table和字符串相差1 if(A.charAt(i-1)==B.charAt(j-1)){
table[i][j] = table[i-1][j-1]+1; } //第三种情况 else{ table[i][j] = table[i-1
][j]>table[i][j-1] ? table[i-1][j] :table[i][j-1]; } } } //end LCS //测试结果 int
count =1; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(table[i][j]==count){
System.out.print(A.charAt(i-1)); count++; } } } System.out.println(); }
显然时间复杂度和空间复杂度都为O(n*m)。

技术
©2019-2020 Toolsou All rights reserved,
王者荣耀背景故事整合痴心妄想随机森林篇 R语言实现用C++跟你聊聊“原型模式” (复制/拷贝构造函数)再见!经典版Edge!PYTHON入门期末复习汇总2021年1月程序员工资统计,平均14915元详解ubuntu14.04如何设置静态IP胡润:中国600万资产“富裕家庭”数量首次突破500万户苹果与日产对话暂停,Apple Car进展如何?