文章内容来自于中国大学mooc的浙江大学的数据结构课程上课内容，以下为本人自己听课整理。

1.1什么是数据结构

没有官方的定义，"数据结构是ADT(抽象数据类型Abstract Data Type)的物理实现"——Clifford A.Shaffer
精心选择的数据结构可以带来最有效率的算法。

例1、如何在书架上摆放图书

这个问题的关键在于两个操作：1、怎么插入。2、怎么找

方法一：随便放，插入简单，但是寻找麻烦。
方法二：按书名的拼音字母顺序排放。
查找时采用二分查找，比较简单，但是插入时，每插入一个新的，它后面的全部都得往后移一位，很麻烦。
方法三：把书架划分为几块区域，每块区域指定摆放某种类别的图书；在某种类别内，按照书名的拼音字母顺序摆放。
操作：先定类别，再二分查找
问题：空间如何分配？类别应该分多细？

“解决问题方法的效率跟数据的组织方式有关”

例2、写程序实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印从1到N的全部正整数。

循环实现：

def PrintN(N):
  for i in range(1,N+1):
    print(i)

递归实现：

def Print(N):
  PrintN(N-1)
  print(N)

第二段看着很简洁，漂亮，但是计算机并不喜欢这样的东西，当N很大的时候，内存迟迟得不到释放，就会爆炸。

解决问题方法效率，跟空间效率有关

例3、写程序计算给定多项式在给定点x处的值

秦九韶算法比一般的逐项次方相加要快的多

所以，到底什么是数据结构？

数据对象在计算机中的组织方式：
包括逻辑结构和物理存储结构
例1中方法二代表的是线性结构，方法三代表的是树结构，而如果想要记录哪些人买了同一本书，一个人买了哪些书，则要用到图结构。
数据对象必定与一系列加在其上的操作相关联
完成这些操作所用的方法就是算法

如何描述数据结构

抽象的数据类型(Abstract Data Type)

数据类型

数据对象集
数据集合相关联的操作集

抽象：描述数据类型的方法不依赖于具体实现

与存放数据机器无关
与数据存储物理结构无关
与实现操作的算法和编程语言无关

例4、“矩阵”的抽象数据类型定义

类型名称：矩阵(Matrix)
数据对象集：一个 $M\times N$ 矩阵 $A_{M\times N}=(a_{ij})$ 由 $M\times N$ 个三元组 $(a,i,j)$ 组成，其中 $a$ 是矩阵元素的值， $i$ 是元素所在的行号， $j$ 是元素所在的列号。
操作集：矩阵的生成、相加、相乘 $\ldots$

1.2什么是算法

算法(Algorithm)

一个有限指令集
接受一些输入(有些情况下不需要输入)
产生输出
一定在有限步骤之后停止
每一条指令必须
①有充分明确的目标，不可以有歧义
②计算机能处理的范围之内
③描述应不依赖于任何一种计算机语言以及具体实现手段

什么是好的算法

空间复杂度 $S(n)$ ——占用存储单元的长度
时间复杂度 $T(n)$ ——耗费时间的长度
例2中递归调用 $S(N)=CN$
例3一般逐项相加 $T(n)=c_1n^2+c_2n$ （乘法耗时比加减法多得多，所以在计算复杂度时一般数乘法数量）

在分析一般算法的效率时，我们经常关注下面两种复杂度：

最坏情况复杂度 $T_{worst}(n)$
*平均复杂度 $T_{avg}(n)$

$T_{avg}(n)\leq T_{worst}(n)$

复杂度的渐进表示法

$T(n)=O(f(n))$ 表示存在常数 $C>0,n_0>0$ 使得当 $n\geq n_0$ 时有 $T(n)\leq Cf(n)$
$T(n)=\Omega (f(n))$ 表示存在常数 $C>0,n_0>0$ 使得当 $n\geq n_0$ 时有 $T(n)\leq Cf(n)$
$T(n)=\Theta(h(n))$ 表示存在常数 $C>0,n_0>0$ 使得当 $n\geq n_0$ 时有 $T(n)= O(h(n)),T(n)=\Omega (h(n))$

复杂度分析小窍门

若两段算法分别有复杂度 $T_1(n)=O(f_1(n))$ 和 $T_2(n)=O(f_2(n))$ 则
$T_1(n)+T_2(n)=max(O(f_1(n),O(f_2(n))))$
$T_1(n)\times T_2(n)=O(f_1(n)\times f_2(n))$
若 $T(n)$ 是关于 $n$ 的 $k$ 阶多项式，那么 $T(n)=\Theta(n^k)$
一个 $for$ 循环的时间复杂度等于循环次数乘以循环体代码的复杂度
$if-else$ 结构的复杂度取决于 $if$ 的条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者最大。

1.3应用实例：

最大子列问题

问题描述

给定N个整数的序列 $\{A_1,A_2,\ldots,A_N\}$ 求函数 $f(i,j)=max\{0,\sum_{k=i}^j A_k\}$ 的最大值

算法一

直接三重循环，选头，再选尾，再从头加到尾。 $T(N)=O(N^3)$

算法二

优化了从头加到尾的环节，没有必要这样，尾在向后移动时，只需在和中多加一项即可。

def max(A):
  MaxSum=ThisSum=0
  for i in range(0,N):
    ThisSum=0
    for j in range(i,N):
      ThisSum+=A[j]
      if (ThisSum>MaxSum):
        MaxSum=ThisSum
  return MaxSum

此时 $T(N)=O(N^2)$

算法三

作为一个程序猿(假装是),看到 $N^2$ 复杂度，应该本能想到能否再降。此处采用分而治之的思想来解决这个问题：

用二分法，分别找出左边右边和横跨分割线的部分和的最大值
从单个，到2个到4个 $\ldots$ 最后比较里面的最大值
递归算法复杂度分析：
$T(N)=2T(N/2)+CN,T(1)=O(1)$
$=2(2T(N/2^2)+CN/2)+CN$
$=2^kO(1)+ckN$
$=(ck+1)N$
$=O(NlogN)$

算法四

在线处理：

def Max4(A,N):
  ThisSum=MaxSum=0
  for i in range(0,N):
    ThisSum+=A[i]
    if(ThisSum>MaxSum):
      MaxSum=ThisSum
    elif(ThisSum<0):
    ThisSum=0
  return MaxSum

这个算法将复杂度直接降到 $O(N)$ 但是降低了正确性的判断，对于不懂其中数学机理的人，这个代码是否正确是相当难以判断的。

一、基本概念