数据结构第一讲

数据结构定义

算法的定义

什么是好算法？

空间复杂度

时间复杂度

例子1

打印1到N之间的正整数
有递归和循环两种方法实现。
但是在数字变大后，递归的方法会导致内存占用过多而崩溃。
而循环则不会

例子2 写程序给定多项式在X处的值

从里往外算的算法，不断提出一个X，然后从里往外算。

ElementType Max( ElementType S[], int N )
{int i = 0;float max = S[0];for (i = 1; i < N; i++){if (max < S[i]){max = S[i];}}return max;
}

从外往里算，复杂度高o(n的平方)。

例子3 给定N个整数的序列，求连续的最大子序列的值

1.三层for循环暴力

int MaxSubsequSum(int A[], int N)
{int i = 0;int j = 0;int k = 0;int ThisSum = 0;int MaxSum = 0;for (i = 0; i < N; i++){for (j = i; j < N; j++){ThisSum = 0;for (k = j; k < j; k++){ThisSum += A[i];if (ThisSum > MaxSum){MaxSum = ThisSum;}}}}
}

2.两层for循环暴力

int MaxSubseqSum(int A[], int N)
{int i = 0;int j = 0;int k = 0;int ThisSum = 0;int MaxSum = 0;for (i = 0; i < N; i++){ThisSum = 0;for (j = i; j < N; j++){ThisSum += A[i];if (ThisSum > MaxSum){MaxSum = ThisSum;}}}
}

3.分而治之，递归解决

4.在线处理

每输入一个数据都能即时处理， 在任何一个地方中止输入，都能正确给出当前的解。

int MaxSubseqSum(int A[], int N)
{int i = 0;int MaxSum = 0;int ThisSum = 0;for (i = 0; i < N; i++){ThisSum += A[i];if (ThisSum > MaxSum){MaxSum = ThisSum;}else if (ThisSum < 0){ThisSum = 0;}}return MaxSum;
}