手记

简单数据结构(1)

数据结构

  • 当我们去组织一个数据时,我们要先确定它的数据规模。
  • 不同规模的问题,它处理的难度就不一样。
  • 解决问题方法的效率,要从空间复杂度和时间复杂度两方面衡量

比如一个问题: 给定多项式再给定点x处的值:

方法一(不专业):f(x) = a0 + a1x + … + a(n-1)x^(n-1) + anx^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) = a0 + x(a1 + x( …(a(n-1) + x(an))…))
每次将x当作公因子提取出来,然后从最里层往外层计算

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;
}

概念:数据结构:数据对象在计算机中的组织方式(逻辑结构)。数据对象必定与一系列加在其上的操作相关联。完成这些操作所用的方法就是算法。
抽象数据类型(Abstract Data Type) 确实就是说的类

  • 数据类型
    • 数据对象集
    • 数据集合相关联的操作集
  • 抽象:描述数据类型的方法不依赖于具体实现
    • 与存放数据的机器无关
    • 与数据存储的物理结构无关
    • 与实现操作的算法和编程语言均无关

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

复杂度的渐进表示法

  • O(f(n))表示f(n)是T(n)的某种上界
  • Ω(g(n))表示g(n)是T(n)的某种下界

时间复杂度的感性认知


算法复杂度分析小窍门

若两段算法分别有复杂度T1(n)=O(f1(n))和T2(n)=O(f2(n)),则

  • T1(n)+T2(n)=max( O(f1(n)),Of2(n)))
  • T1(n)×T2(n)=O(f1(n)×f2(n))
  • 一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度
  • if-else结构的复杂度取决于if的条件判断复杂度和两个分枝部分的复杂度,总体复杂度取三者中最大

最大子列和

给定N个整数的序列{A1,A2……A},求函数f(i,j)的最大值。

方法一:暴力 O(n^3)

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;  
}

方法二: O(n2)

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;  
}

方法二: 分治法(归并)

更快的算法:在线处理算法 O(n)

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;  
}
0人推荐
随时随地看视频
慕课网APP