简单数据结构（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;  
}