1、基本概念

1.1 数据结构与算法概述

–解决问题的方法
解决问题方法的效率，跟时间效率有关；
解决问题方法的效率，跟空间的利用效率有关；–比如，递归调用可能将内存空间消耗殆尽。
解决问题方法的效率，跟算法的巧妙程度有关。

例如，计算多项式的算法：写程序计算给定多项式在给定点x = 1.1 处的值f(1.1)。

//方法一
double f1( int n, double a[], double x )
{ int i;
    double p = a[0];
    for ( i=1; i<=n; i++ )
        p += (a[i] * pow(x, i));
    return p;
}
//方法二
double f2( int n, double a[], double x )
{ int i;
    double p = a[n];
    for ( i=n; i>0; i-- )
        p = a[i-1] + x*p;
    return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

什么是数据结构

–数据对象在计算机中的组织方式；数据对象必定与一系列加在其上的操作相关联，完成这些操作所使用的方法就是算法。
什么是数据对象的逻辑结构？
一对一的结构，叫线性结构；一对多的逻辑结构，叫树；多对多的、复杂的关系网，这个关系网对应的结构，叫图。
数据对象在计算机中的物理存储结构，在内存里的具体怎么放，数组（连续着放），链表。
描述数据结构有一张方法，叫抽象数据类型（Abstract Data Type）:
（1）数据类型

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

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

• 与存放数据的机器无关；
• 与数据存储的物理结构无关；
• 与实现操作的算法和编程语言均无关。
• 只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题。

例子：说明什么是抽象数据类型

//矩阵的抽象数据类型定义

(1)类型名称：矩阵（Matrix）
(2)数据对象集：一个M*N的矩阵AMxN = (aij) (i=1, …, M; j=1, …, N
)由MxN个三 元组< a, i, j >构成，其中a是矩阵元素的值，i是元素所在的行号，j是元素 所在的列号。
(3)操作集：对于任意矩阵A、B、C 属于 Matrix，以及整数i、j、M、N
Matrix Create( int M, int N )：返回一个MxN的空矩阵；
int GetMaxRow( Matrix A )：返回矩阵A的总行数；
int GetMaxCol( Matrix A )：返回矩阵A的总列数；
ElementType GetEntry( Matrix A, int i, int j )：返回矩阵A的第i行、第j列的元素；
Matrix Add( Matrix A, Matrix B )：如果A和B的行、列数一致，则返回矩阵C=A+B，否则返回错误标志；
Matrix Multiply( Matrix A, Matrix B )：如果A的列数等于B的行数，则返回矩阵C=AB，否则返回错误标志；
……

抽象1：矩阵元素类型，不必要具体指定是int还是double等；
抽象2：矩阵维度，是二维数组，还是一维数组或十字链表，不关心它是怎么实现的，只要实现的是一个矩阵；
抽象3：比如实现矩阵相加Add，只要返回矩阵相加后的结果，不用指定先按行加？先按列加？用什么语言；
等等。

抽象的好处：
抽象可以有助于形成程序思路，只关注大致步骤，具体步骤如何实现可以先不考虑，从而使得程序思路容易看懂，而不用过分钻研细节
使用抽象数据类型有如下好处：
1.可以隐藏实现细节；
2.改动不会影响到整个程序；
3.让接口能提供更多信息；
4.更容易提高性能；
5.让程序的正确性显而易见；
6.程序更具有自我说明性；
7.无需在程序内到处传递数据；
8.可以以更接近现实世界中的方式去操作，而不是去操作底层，比如数组、队列、栈等，而是更具体的好理解的功能名称。

什么是算法

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

例1：选择排序算法的伪代码描述

void SelectionSort ( int List[], int N )
{ /* 将N个整数List[0]...List[N-1]进行非递减排序*/
    for ( i = 0; i < N; i ++ ) {
        MinPosition = ScanForMin( List, i, N–1 );
        /* 从List[i]到List[N–1]中找最小元，并将其位置赋给MinPosition */
        Swap( List[i], List[MinPosition] );
        /* 将未排序部分的最小元换到有序部分的最后位置*/
    }
}
1
2
3
4
5
6
7
8
9

抽象 – 不关心具体实现的细节
（1）List到底是数组还是链表（虽然看上去像数组）？
（2）Swap用函数还是用宏实现？

什么是好的算法？
空间复杂度S(n) —— 根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。
时间复杂度T(n) —— 根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。

例2：递归调用输出小于N的所有整数

void PrintN ( int N )
{ 	
	if ( N )
	{
		PrintN( N – 1 ); printf(“%d\n”, N );
	}
	return;
}
1
2
3
4
5
6
7
8

内存空间占用：每次递归需要分配一块内存

//递归执行过程
PrintN(100000)
    PrintN(99999)
        PrintN(99998)
            PrintN(99997)
                …… ……
                            PrintN(0)
1
2
3
4
5
6
7

每次递归都会申请占用一块内存，若N=100000，则程序可能要爆掉。

例3：计算多项式的两种方法（计算机运算加减法比乘除法快得多）

double f( int n, double a[], double x )
{     int i;
        double p = a[0];
        for ( i=1; i<=n; i++ )      	//(1+2+……+n)
            p += (a[i] * pow(x, i));  	//=(n^2+n)/2次乘法
        return p;
} //时间复杂度T(n) = C1*n^2+C2*n

double f( int n, double a[], double x )
{ int i;
    double p = a[n];
    for ( i=n; i>0; i-- )
        p = a[i-1] + x*p;              //n次乘法！
    return p;
} //时间复杂度T(n) = C *n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在分析一般算法的效率时，我们经常关注下面两种复杂度：
（1）最坏情况复杂度Tworst( n )
（2）平均复杂度Tavg( n )
但通常平均复杂度是难以估计的，往往是计算最坏复杂度，Tavg( n ) <= Tworst( n )

复杂度的渐进表示法（不需要精确的表示，只需要了解算法的增长率）
（1）T(n) = O(f(n)) 表示存在常数C >0, n0>0 使得当n>=n0 时有T(n) <= C·f(n) -->简单来说就是，O(f(n))表示f(n)是T(n)的某种上界；
（2）T(n) = Ω(g(n)) 表示存在常数C >0, n0>0 使得当n>=n0 时有T(n) >=C·g(n) -->Ω(g(n))表示g(n)是T(n)的某种下界；
（3）T(n) = Θ(h(n)) 表示同时有T(n) = O(h(n)) 和T(n) = Ω(h(n)) -->Θ(h(n))表示O和Ω是同时成立的，也就是说，它既是上界也是下界，它们基本上是等价的。
对于一个函数的上界和下界来说并不是唯一的，但是对于太大的上界和太小的下界，对分析一个算法的效率是没有什么帮助的，尽可能最贴近的。

输入规模n

复杂度分析小窍门
（1）若两段算法分别有复杂度T1(n) = O(f1(n)) 和T2(n) =O(f2(n))，则
T1(n) + T2(n) = max( O(f1(n)), O(f2(n)) )
T1(n) ´ T2(n) = O( f1(n) * f2(n) )
（2）若T(n)是关于n的k阶多项式，那么T(n)=Θ(n^k)
（3）一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度
（4）if-else 结构的复杂度取决于if的条件判断复杂度和两个分枝部分的复杂度，总体复杂度取三者中最大

1.2 应用实例：最大子列和问题

给定N个整数的序列{ A1, A2, …,
AN}，求函数
的最大值。

算法1：

算法2：

算法3：

算法4：在线处理

“在线”的意思是指每输入一个数据就进行即时处理，在任何一个地方中止输入，算法都能正确给出当前的解。

运行时间比较（单位秒）