数据结构班-第1课-算法初步-课堂笔记


第1课 算法初步

算法研究的是,时间和空间的复杂度。

算法的特点:
  • 有穷性。
  • 确定性。
  • 可行性。
  • 输入 & 输出。


算法有哪些?
  • 穷举(最慢,最没有技术含量,但是有最全的)。
  • 分而治之。
  • 贪心:最小生成树。
  • 动态规划:背包,士兵路径。


谈算法不谈复杂度=耍流氓。
硬件发展,速度提升,内存提升(常数级)
在实现之前,我们要预估算法所需要使用的资源:
  • 时间。
  • 空间。


假设计算机一秒钟能跑一亿条高级指令。

输入输出法。

均摊分析。

vector 扩增。

如果满了,那么申请一个双倍容量的,然后复制原来的数据,删除原来的空间。

假设系统开空间的时间复杂度为 \(O(1)\),那么复制 \(O(k)\)。

在有空间的情况下,插入数据的时间复杂度为 \(O(1)\),在空间满了,重新申请内存,然后逐项复制 \(O(n)\)。

去掉冗余的思想去理解动态规划。

优化目标:

$${\max_{i, j} (a[i] + a[i+1] + \cdots + a[j])}$$

设定:

$${s[i] = a[0] + a[1] + \cdots + a[i]}$$

优化目标修改为:

$${\max (s[j] - s[i-1])}$$

此时,固定 \(s[j] = p\),

则优化目标修改为:

$${\min s[i-1] \ \ \ \ s.t. \ \ i < j}$$

所有优化的代码为:

053. Maximum Subarray
class Solution {
public:
    // 程序的时间复杂度不对。O(n^3),附加空间复杂度O(1)。
    int maxSubArray(vector<int> &nums) {
        int n = nums.size();
        int ans = INT_MIN;  // INT 最小的数据。
        for (int st = 0; st < n; ++st) {
            for (int ed = st + 1; ed <= n; ++ed) {
                int sum = 0;
                for (int i = st; i < ed; ++i) {
                    sum += nums[i];  // 优化先找最内层的循环,执行次数最多,累计求和,是优化的方向。
                }
                if (sum > ans) {
                    ans = sum;
                }
            }
        }
        return ans;
    }

    // 去掉了 sum 的冗余,每一个数字会被加入到 sum,累计 st 到 ed。
    int maxSubArray_better(vector<int> &nums) {
        int n = nums.size();
        int ans = INT_MIN;  // INT 最小的数据。

        for (int st = 0; st < n; ++st) {
            int sum = 0;
            for (int ed = st + 1; ed <= n; ++ed) {
                sum += nums[ed - 1];
                if (sum > ans) {
                    ans = sum;
                }
            }
        }
        return ans;
    }

    // 求和变成求差,求最大变成最小。
    int maxSubArray_best(vector<int> &nums) {
        int ans = INT_MIN;  // 设置最小值。
        int n = nums.size();

        int s = new int[n + 1]; // 求和数组,存储部分和。
        s[0] = 0; // 表示没有数字。
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + nums[i]; // s[i] 表示前 i 个数字的和。
        }

        for (int j = 0; j < n; j++) { // 固定 j,寻找最小的 i。
            int min = 0;
            for (int i = 0; i < j; i++) { // 每次 j 增加,i 又从 0 开始遍历,这里有冗余。
                if (s[i] < min) {
                    min = s[i];
                }
            }
            if (s[j] - min > ans) {
                ans = s[j] - min;
            }
        }

        return ans;
    }

    // 化简写法。
    int maxSubArray_best_opt(vector<int> &nums) {
        int ans = INT_MIN;  // 设置最小值。
        int n = nums.size();
        int sj = 0;
        int si = 0;
        int minSi = 0;
        // min[0, 6] = min(min[0, 5], min[6, 6])
        // 求和变求差,求积变求和。
        // 在一次遍历中,j 比 i 跑得快,由于 i 跑得慢,需要需要记录最小的前 i 项和,
        // 同时每次遍历的时候,记录最大的前 j 项和。
        for (int j = 0; j < n; j++) {
            sj += nums[j];

            if (si < minSi) {
                minSi = si;
            }

            if (sj - minSi > ans) {
                ans = sj - minSi;
            }
            si += nums[j];
        }
        return ans;
    }

    int maxSubArray_best_opt_opt(vector<int> &nums) {
        int ans = INT_MIN;  // 设置最小值。
        int n = nums.size();

        int sum = 0; // 数组的前 j 项和。

        for (int j = 0; j < n; j++) {
            sum += nums[j]; // 累计前 j 项和。

            if (sum > ans) { // 如果求和大于了设定值,那么更新。
                ans = sum;
            }

            if (sum < 0) {
                sum = 0;
            }
        }
        return ans;
    }
};


课后题目:152. Maximum Product Subarray
class Solution {
public:
    int maxProduct(vector<int> &nums) {
        int n = nums.size();
        int ans = INT_MIN;

        if (0 == n) {
            return 0;
        }

        if (1 == n) {
            return nums[0];
        }

        // 因为考虑到符号问题。
        int maxLast = nums[0]; // 记录乘到上个元素的最大乘积。
        int minLast = nums[0]; // 记录乘到上个元素的最小乘积。
        int maxCur; // 记录乘到当前元素的最大乘积。
        int minCur; // 记录乘到当前元素的最小乘积。
        int maxAll = nums[0]; // 记录全局最大的乘积。
        for (int i = 1; i < n; i++) {
            maxCur = max(nums[i], max(maxLast * nums[i], minLast * nums[i]));
            minCur = min(nums[i], min(maxLast * nums[i], minLast * nums[i]));
            maxLast = maxCur;
            minLast = minCur;
            maxAll = max(maxAll, maxCur);
        }

        return maxAll;
    }
};
已邀请:

要回复问题请先登录注册

返回顶部