@guoxs 2015-10-18T17:14:45.000000Z 字数 4347 阅读 2973

数据结构与算法（一）

数据结构与算法

数据结构与算法（一）

1、数据结构定义

数据对象在计算机中的组织方式

逻辑结构
物理存储结构

数据对象必定与一系列加在其上的操作相关联
完成这些操作所用的方法就是算法

抽象数据类型（Abstract Data Type）
数据类型

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

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

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

只描述数据对象集和相关操作集“是什么”，并不涉及
“如何做到”的问题

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

类型名称：矩阵（Matrix）
数据对象集：一个M×N的矩阵 $A_{M×N} = (a_{ij}) (i=1, …, M; j=1, …, N )$ 由M×N个三元组< a, i, j >构成，其中a是矩阵元素的值，i是元素所在的行号，j是元素所在的列号。
操作集：对于任意矩阵A、B、C属于Matrix，以及整数i、j、M、N

Matrix Create( int M, int N )：返回一个M×N的空矩阵；
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，否则返回错误标志；

抽象在于：
矩阵中a类型不确定，二维数组？一位数组？十字链表？
运算的规则未确定，先按行加？先按列加？什么语言？

2、算法

算法（Algorithm）

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

算法的伪码描述

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] );
        /* 将未排序部分的最小元换到有序部分的最后位置*/
    }
}

抽象性在于：
List到底是数组还是链表（虽然看上去很像数组）？
Swap用函数还是用宏去实现？

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

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

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

T w o r s t (n) > = T a v g (n)

$T_{worst}( n ) >= T_{avg}( n )$

复杂度的渐进表示法
$T(n) = O(f(n))$ 表示存在常数 $C>0, n_0>0$ 使得当
$n >= n_0 时有T(n) <= C·f(n)$

$T(n) = Ω(g(n))$ 表示存在常数 $C >0, n_0>0$ 使得当
$n>=n_0 时有T(n) >= C·g(n)$

$T(n) = Θ(h(n))$ 表示同时有 $T(n) = O(h(n))$ 和
$T(n) = Ω(h(n))$

常见算法复杂度函数排序：

l o g n > n > n l o g n > n 2 > n 3 > 2 n > n!

$logn > n >nlogn > n^2 > n^3 > 2^n > 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) × T_2(n) = O( f_1(n) × f_2(n) )$

若T(n)是关于n的k阶多项式，那么 $T(n)=Θ(nk)$

一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度

if-else 结构的复杂度取决于if的条件判断复杂度和两个分枝部分的复杂度，总体复杂度取三者中最大

3、循环与递归

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

循环实现：

void PrintN ( int N ){
    int i;
    for ( i=1; i<=N; i++ ){
        printf(“%d\n”, i );
    }
    return;
}

递归实现：

void PrintN ( int N ){
    if ( N ){
        PrintN( N – 1 );
        printf(“%d\n”, N );
    }
    return;
}

递归实现简单，代码简洁，但是有一个致命的问题，那就是空间占用太大。当N很大时，需要花费很大的内存来存储中间变量，易导致计算机崩溃！

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

f (x) = a 0 + a 1 x + \cdot \cdot \cdot + a n - 1 x n - 1 + a n x n

$f(x)=a_0+a_1x+···+a_{n-1}x^{n-1}+a_nx^n$

double f( 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;
}

另一种更优算法：

f (x) = a 0 + x (a 1 + x (\cdot \cdot \cdot （ a n - 1 + x (a n) ）))

$f(x)=a_0+x(a_1+x(···（a_{n-1}+x(a_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;
    }
    return p;
}

4、clock()函数

clock()：捕捉从程序开始运行到clock()被调用时所耗费的时间。这个时间单位是clock tick，即“时钟打点”。
常数CLK_TCK(或CLOCKS_PER_SEC)：机器时钟每秒所走的时钟打点数。每台机器该值不一样。

用clock()函数比较两个算法所花的时间：

#include <stdio.h>
#include <time.h>
clock_t start, stop;
/* clock_t是clock()函数返回的变量类型*/
double duration;
/* 记录被测函数运行时间，以秒为单位*/
int main (){
/* 不在测试范围内的准备工作写在clock()调用之前*/
    start = clock();/* 开始计时*/
    MyFunction();/* 把被测函数加在这里*/
    stop = clock();/* 停止计时*/
    duration = ((double)(stop - start))/CLK_TCK;
    /* 计算运行时间*/
    /* 其他不在测试范围的处理写在后面，例如输出duration的值*/
    return 0;
}

解决问题方法的效率

数据的组织方式有关
空间的利用效率有关
算法的巧妙程度有关

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

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

算法1：

int MaxSubseqSum1( int A[], int N ){
    int ThisSum, MaxSum = 0;
    int i, j, k;
    for( i = 0; i < N; i++ ) { /* i是子列左端位置*/
        for( j = i; j < N; j++ ) { /* j是子列右端位置*/
            ThisSum = 0; /* ThisSum是从A[i]到A[j]的子列和*/
            for( k = i; k <= j; k++ )
                ThisSum += A[k];
            if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大*/
                MaxSum = ThisSum; /* 则更新结果*/
            } /* j循环结束*/
        } /* i循环结束*/
    return MaxSum;
}

$T( N ) = O( N^3 )$

算法2:

int MaxSubseqSum2( int A[], int N ){
    int ThisSum, MaxSum = 0;
    int i, j;
    for( i = 0; i < N; i++ ) { /* i是子列左端位置*/
        ThisSum = 0; /* ThisSum是从A[i]到A[j]的子列和*/
        for( j = i; j < N; j++ ) { /* j是子列右端位置*/
            ThisSum += A[j];
/*对于相同的i，不同的j，只要在j-1次循环的基础上累加1项即可*/
        if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大*/
            MaxSum = ThisSum; /* 则更新结果*/
        } /* j循环结束*/
    } /* i循环结束*/
    return MaxSum;
}

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

算法3：分而治之
分治法

算法4：在线处理

int MaxSubseqSum4( int A[], int N ){
    int ThisSum, MaxSum;
    int i;
    ThisSum = MaxSum = 0;
    for( i = 0; i < N; i++ ) {
        ThisSum += A[i]; /* 向右累加*/
        if( ThisSum > MaxSum )
            MaxSum = ThisSum; /* 发现更大和则更新当前结果*/
        else if( ThisSum < 0 ) /* 如果当前子列和为负*/
            ThisSum = 0; /* 则不可能使后面的部分和增大，抛弃之*/
        }
    return MaxSum;
}

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