- 什么是数据结构？
- 数据对象 在计算机中的组织方式。
逻辑结构（线性结构，树型结构，图结构）
物理存储结构（在内存里的放法） - 数据对象必定与一系列加在其上的操作关联。
- 完成这些操作所用的方法叫算法。
- 描述数据结构的用 抽象 数据类型 （abstract data type）
数据类型：
- 数据对象集
- 数据集合相关操作表
抽象：描述数据类型的方法不依赖具体实现.
3.什么是算法：
- 一个有限的指令集
- 接受一些输入
- 产生输出
- 有限步骤后终止
- 每一条指令必须 明确，计算机能处理的范围内，不依赖任何一种计算机语言。
- 什么是好的算法：
- 空间复杂度：S(n) 算法执行时 占用存储单元的长度，这个长度往往与输入数据的规模有关。
- 时间复杂度：T(n) 执行时耗费时间的长度。
复杂度的渐进表示法
直观感受
分析小窍门
例题给定N个整数的序列{ A1, A2, ..., AN}， j
求函数 f(i,j)=max{0,A}
的最大值：
算法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;
}
// 3个for循环，所以是n的立方 T(n) = O(N立方)
算法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;
}
// 优化，2个for循环，复杂度为O(N平方)
算法3：
再优化，分而治之, 使用递归，时间辅助度是O(nlogn)
最优的算法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;
}
//时间复杂度为O(n)
