数据结构与算法学习之路--1、绪论

该博客为数据结构与算法课程的学习笔记！

(a) 计算

计算 = 信息处理：借助某种工具，遵照一定的规则，以明确而机械的方式进行。

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

算法： 即在特定的计算模型下，旨在解决特定问题的指令序列。

1. 正确性：的确可以解决的问题。
2. 确定性：任意算法都可以描述成一个由基本操作组成的序列。
3. 可行性：每一基本操作都可以实现，且在常数时间内完成。
4. 有穷性：对于任意输入，经有穷次基本操作都可以得到输出。

(b) 计算模型

T(n) : 用算法A求解某一问题规模为n的实例所需的计算成本

$$T(n)=max [T(p)| |p|=n)]$$

​ 亦即：在规模同为n的所有实例中，只关注最坏（成本最高）者。

T(n)=算法为解决规模为n的问题所需的基本操作次数。

(c) 大o记号

$$T(n) =o(f(n))$$

f(n)相对于T(n)更加简洁，但依旧可以反映后者的增长趋势。f(n)常系数可以忽略，低次项可以忽略。

$o(1)$=任意常数: 此类算法效率最高，是对数据结构的基本操作，其代码一定满足以下：

• 一定不含循环
• 一定不含分支转向
• 一定不能有递归调用

对数复杂度$o(log n)$: 其值与常底数无关、与常数次幂无关，此类算法非常有效，复杂度无限接近常数。有序向量的二分查找 堆、词典的查询、插入与删除。

多项式复杂度$o(n^c)$：此类算法的效率通常认为已可令人满意。其中：线性复杂度o(n)属于努力的目标，如树图的遍历；平方复杂度存在于所有输入对象两两组合，如Dijkstra算法；立方复杂度不常见，如矩阵乘法。

​ $o(n log^*n)$几乎接近线性,某些MST算法。

​ $o(nlogn)$最常出现，但未必最优，排序，EU，Huffman算法。

指数复杂度$o(2^n)$:此类算法计算成本增长极快，通常被认为不可接受。最平凡的算法，需要尽可能的优化。

从$o(n^c)$到$o(2^n)$，是从有效算法到无效算法的分水岭。

对于绝大多数问题，并不存在算法！！！

(d)算法分析

算法分析的主要任务分为：正确性（不变性x单调性） + 复杂度

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

复杂度分析的方法：

​ 迭代：级数求和

​ 递归：递归跟踪+递推方程

​ 猜测+验证

级数：

• 对于算术级数，复杂度与末项平方同阶：$T(n)=1+2+3+···+n=n(n+1)/2=o(n^2)$
• 对于幂次级数，复杂度比幂次高出一阶：$T(n)=\sum k^n=\int k^ndn=o(k^(n+1))$
• 对于几何级数（a>1），复杂度与末项同阶：$T(n)=\sum_{i=0}^{i=n} a^i=o(a^n)$

(e)递归与迭代

1. 数组求和之线性递归：

   int sum(int A[],int n)	//计算数组中n个数的和
   {
       if (n<1){ return 0;}
       else {
       return A[n-1]+sum(A,n-1);
       }   
   }

2. 数组求和之二分递归：

   int sum(int A[],int a ,int b)
   {
      if(a==b) return A[a];
       int mid=(a+b)/2;
       return (sum(A,a,mid)+sum(A,mid+1,b));
   }

(f)局限

RAM模型：常数代价准则、对数代价准则

循环移位：

void shift(int *A,int n,int k){
    reverse(A,k);
    reverse(A+k,n-k);
    reverse(A,n);
}