[数据结构与算法]听课笔记——陈越老师《数据结构》第一章

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

1. 数据类型

1. 数据对象集
2. 数据集合相关联的操作集

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

1. 与存放数据的机器无关
2. 与数据存储的物理结构无关
3. 与实现操作的算法和编程语言均无关

二、算法（Algorithm）

1. 一个有限的指令集
2. 接受一些输入（有些情况下不需要输入）
3. 产生输出
4. 一定在有限步骤后终止
5. 每一条指令必须
   有充分明确的目标，不可以有歧义
   计算机能处理的范围之内
   描述应不依赖于任何一种计算机语言以及具体的实现手段

三、算法的复杂度

1. 空间复杂度S(n): 根据算法写成的程序在执行时占用储存单元的长度。
2. 时间复杂度T(n): 根据算法写成的程序在执行时消耗时间的长度。(另: 若一个算法的时间复杂度为n²，应想办法将其降为nlog(n))

四、应用实例：最大子列和问题

算法1: T(n) = O(n³)

int maxSubseqSum1(int arr[], int n)  // 算法1, T(n) = O(n^3)
{
    int maxSum{}, thisSum;  // thisSum表示当前求得的子列和
    for (int i{}; i< n; i++) {  // i表示子列左端
        for (int j{i}; j< n; j++) { // j表示子列右端
            thisSum = 0;
            for (int k{i}; k <=j; k++) {
                thisSum += arr[k];
            }
            if (thisSum> maxSum) {  // 若当前子列和比之前记录的最大子列和更大
                maxSum = thisSum;   // 则更新最大子列和
            }
        }
    }
    return maxSum;
}

算法2: T(n) = O(n²)

int maxSubseqSum2(int arr[], int n)
{
    int maxSum{}, thisSum;  // thisSum表示当前求得的子列和
    for (int i{}; i< n; i++) {  // i表示子列左端
        thisSum = 0;
        for (int j{i}; j< n; j++) {
            thisSum += arr[j];
            if (thisSum> maxSum) {  // 若当前子列和比之前记录的最大子列和更大
                maxSum = thisSum;   // 则更新最大子列和
            }
        }
    }
    return maxSum;
}

算法3(分而治之): T(n) = O(nlog(n))
将数组从中间分开处理，分别计算左右两半边的最大子列和，同时计算跨越中间区域的最大子列和，返回这三者中的最大值。
其时间复杂度等于处理左右半边的时间复杂度加上处理跨区元素的时间复杂度（三部分之和），即(假设处理一个元素的时间复杂度T(1) = O(1)):
T(n)
= T(n / 2) + T(n / 2) + O(n)
= 2 * T(n / 2) + c * n 注: 这里(c * n)为n的常数倍，即处理n个O(1)所需的时间
= 2 * [2 * T(n / 2²) + c * (n / 2)] + c * n
= 2²T(n / 2²) + 2 * c * n
以此类推，假设经过k步调用后需处理的元素只剩下一个，有:
T(n)
= 2^kT(n / 2^k) + k * c * n 其中: n / 2^k = 1
= n * O(1) + c * n * log(n)
= O(n) + O(nlog(n))
当两个不同的复杂度加在一起时，取较大的那一项，所以:
T(n) = O(nlog(n))

int maxSubseqSum3(int arr[], int fir, int last)
{
    if (fir == last) {  // 若递归至只用处理一个元素
        return arr[fir];    // 则返回那一个元素
    }
    int leftMax, rightMax, maxSum{};    // leftMax表示左边的最大子列和, rightMax表示右边的最大子列和
    leftMax = maxSubseqSum3(arr, fir, (fir + last) / 2);    // 递归调用
    rightMax = maxSubseqSum3(arr, (fir + last) / 2 + 1, last);
    for (int i{(fir + last) / 2}, thisSum{arr[i]}; i >=fir; i--, thisSum += arr[i]) {   // 处理跨越中间点的最大子列和，从中间开始往左扫描
        if (thisSum> maxSum) {  // 若当前子列和大于之前记录的最大子列和
            maxSum = thisSum;   // 则更新最大子列和
        }
    }
    for (int i{(fir + last) / 2 + 1}, thisSum{arr[i]}, tmpMaxSum{maxSum}; i <=last; i++, thisSum += arr[i]) {   // 往右扫描, tmpMaxSum记录扫描前maxSum的值
        if (thisSum> maxSum - tmpMaxSum) {  // 若当前子列和大于之前记录的最大子列和
            maxSum = tmpMaxSum + thisSum;   // 则更新最大子列和
        }
    }
    if (leftMax> maxSum) {  // 若左边返回的最大子列和大于之前记录的最大子列和
        maxSum = leftMax;   // 则将leftMax赋值给maxSum
    }
    if (rightMax> maxSum) { // 若左边返回的最大子列和大于之前记录的最大子列和
        maxSum = rightMax;  // 则将rightMax赋值给maxSum
    }
    return maxSum;
}

算法4(在线处理): T(n) = O(n)

int maxSubseqSum4(int arr[], int n)
{
    int maxSum{}, thisSum{};    // thisSum表示当前子列和
    for (int i{}; i< n; i++) {
        thisSum += arr[i];  // 向右累加
        if (thisSum> maxSum) {  // 若当前子列和大于之前记录的最大子列和
            maxSum = thisSum;   // 则更新最大子列和
        }
        if (thisSum< 0) {   // 若当前子列和为负数, 说明其会对后面的子列和起副作用(与后面的子列和结合后会使后面的子列和变小, 所以应使当前子列和清零)
            thisSum = 0;    // 则令当前子列和为0, 并继续计算后面的子列和
        }
    }
    return maxSum;
}