[关闭]
@guoxs 2015-10-18T09:14:45.000000Z 字数 4347 阅读 1778

数据结构与算法(一)

数据结构与算法


1、数据结构定义

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

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

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

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

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

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

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

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

2、算法

算法(Algorithm)

算法的伪码描述

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

抽象性在于:
List到底是数组还是链表(虽然看上去很像数组)?
Swap用函数还是用宏去实现?

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

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

Tworst(n)>=Tavg(n)

复杂度的渐进表示法
T(n)=O(f(n)) 表示存在常数C>0,n0>0使得当
n>=n0T(n)<=Cf(n)

T(n)=Ω(g(n))表示存在常数C>0,n0>0使得当
n>=n0T(n)>=Cg(n)

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

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

logn>n>nlogn>n2>n3>2n>n!

复杂度分析小窍门
若两段算法分别有复杂度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))

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

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

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

3、循环与递归

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

循环实现:

  1. void PrintN ( int N ){
  2. int i;
  3. for ( i=1; i<=N; i++ ){
  4. printf(“%d\n”, i );
  5. }
  6. return;
  7. }

递归实现:

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

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

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

f(x)=a0+a1x++an1xn1+anxn

  1. double f( int n, double a[], double x ){
  2. int i;
  3. double p = a[0];
  4. for ( i=1; i<=n; i++ ){
  5. p += (a[i] * pow(x, i));
  6. }
  7. return p;
  8. }

另一种更优算法:

f(x)=a0+x(a1+x(an1+x(an)))

  1. double f( int n, double a[], double x ){
  2. int i;
  3. double p = a[n];
  4. for ( i=n; i>0; i-- ){
  5. p = a[i-1] + x*p;
  6. }
  7. return p;
  8. }

4、clock()函数

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

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

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

解决问题方法的效率

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

给定N个整数的序列A1,A2,,ANf(x,y)=max0,jk=iAk求函数的最大值。

算法1:

  1. int MaxSubseqSum1( int A[], int N ){
  2. int ThisSum, MaxSum = 0;
  3. int i, j, k;
  4. for( i = 0; i < N; i++ ) { /* i是子列左端位置*/
  5. for( j = i; j < N; j++ ) { /* j是子列右端位置*/
  6. ThisSum = 0; /* ThisSum是从A[i]到A[j]的子列和*/
  7. for( k = i; k <= j; k++ )
  8. ThisSum += A[k];
  9. if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大*/
  10. MaxSum = ThisSum; /* 则更新结果*/
  11. } /* j循环结束*/
  12. } /* i循环结束*/
  13. return MaxSum;
  14. }

T(N)=O(N3)

算法2:

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

T(N)=O(N2)

算法3:分而治之
分治法

算法4:在线处理

  1. int MaxSubseqSum4( int A[], int N ){
  2. int ThisSum, MaxSum;
  3. int i;
  4. ThisSum = MaxSum = 0;
  5. for( i = 0; i < N; i++ ) {
  6. ThisSum += A[i]; /* 向右累加*/
  7. if( ThisSum > MaxSum )
  8. MaxSum = ThisSum; /* 发现更大和则更新当前结果*/
  9. else if( ThisSum < 0 ) /* 如果当前子列和为负*/
  10. ThisSum = 0; /* 则不可能使后面的部分和增大,抛弃之*/
  11. }
  12. return MaxSum;
  13. }

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注