BUAA算法设计与分析（高工）笔记

一、分而治之篇

（零）递归算法的复杂度分析

符号（区分符号）

符号	含义
	函数上界
	函数紧界
	函数下界

递归树法（略）

代入法

先假设，再代入递归式中证明可以用常数限制复杂度函数值域

主定理法

对一般的递归式，设有如下形式：

，下求其复杂度（为其复杂度常数项式，即合并过程中产生的复杂度）

递归中，第一层：、第二层：、第层：，最后一层为(递归终止条件)，深度共

故总复杂度：【递归分裂代价】【合并代价】

而我们有

故可写成的形式：【递归分裂代价】【合并代价】

而对右侧求和式，我们可以将及之后项都向上/下放缩，故我们只需要比较与生成叶结点代价之和

故主定理：

对形如的递归式

而当时，简化有：

拓展形式

（一）归并排序

算法思路

自底向下，每次获取左侧、右侧各一半的部分排序解。两个指针分别指在两侧，依次比较合并成总的排序结果。则合并过程需要扫描整个排序列表，复杂度，递归深度，由递归的主定理，总复杂度

class Solution: # 输入数组为nums，类型为列表
    def merge_sort(self, nums):
        def loop(num):
            if len(num) == 1:
                return num
            num_l = loop(num[0: len(num) // 2])
            num_r = loop(num[len(num) // 2: len(num) + 1])
            p_l, p_r, l_l, l_r, res = 0, 0, len(num_l), len(num_r), []
            while p_l < l_l and p_r < l_r:
                if num_l[p_l] < num_r[p_r]:
                    res.append(num_l[p_l])
                    p_l += 1
                else:
                    res.append(num_r[p_r])
                    p_r += 1
            for i in range(p_l, l_l):
                res.append(num_l[i])
            for i in range(p_r, l_r):
                res.append(num_r[i])
            return res

        return loop(nums)

（二）最大子数组

问题描述

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

算法思路

1.分而治之

每次向下对半拆分递归求解，得到左侧最大，右侧最大，又因为跨左右侧最大子串必是【左侧内部含最右字符最大串】+【右侧内部含最左字符最大串】，只需要遍历整个数组一遍，复杂度，故递归深度，由递归的主定理，总复杂度

#  #  https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
class Solution: # 输入数组为nums，类型为列表
    def devision(self, nums):

        def cal_s3(s_index, mid_index, e_index):
            left_ans, right_ans, var = nums[mid_index], nums[mid_index + 1], nums[mid_index]
            for i in range(mid_index - 1, s_index - 1, -1):
                var += nums[i]
                left_ans = max(var, left_ans)
            var = nums[mid_index + 1]
            for i in range(mid_index + 2, e_index + 1):
                var += nums[i]
                right_ans = max(var, right_ans)
            return left_ans + right_ans

        def divide(l, r):
            if l >= r:
                return nums[l]
            s1 = divide(l, (l + r) // 2)
            s2 = divide((l + r) // 2 + 1, r)
            s3 = cal_s3(l, (l + r) // 2, r)
            return max(s1, s2, s3)

        return divide(0, len(nums) - 1)

2.动态规划

从左到右，依次考虑以第位结尾的子串，这些子串若含第位，则最大值必为以第位为末尾的子串加上数组第项；若不含第位，则子串最大值为数组第项

故从左到右扫描一次数组，记录以指针处为末尾项子串最大值,若小于0，则指针后移时更新最大值为下一位本身，否则记录值与之相加

class Solution:
    def dp(self, nums):
        ans, res = nums[0], nums[0]
        for i in range(1, len(nums)):
            res = max(0, res) + nums[i]
            ans = max(res, ans)
        return ans

（三）逆序对计数问题

问题描述

给定一个数组 ，如果且 我们就将 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

算法思路

应用分治思想，若已知对半分后的两子集和的逆序对个数分别为，则总的逆序对个数为：

式中最后一项描述前一项在、后一项在中的逆序对个数；注意到分组并不会打破组间的相对大小顺序，故合并过程即计算式中最后一项只需找出迁移组中比后一组中数字大的对数即可；为了简化这一步的复杂度，我们联想到了排序，若排好序的,只需通过依次扫描就可找出所有的逆序对，故联想到归并排序，此算法只需要在归并的基础上加上逆序对计数即可

#  https://leetcode.cn/problems/reverse-pairs
class Solution:
    def reversePairs(self, nums):
        ans = 0

        def compare(num_l, num_r):
            res, p_l, p_r, cnt = [], 0, 0, 0
            while p_l < len(num_l) and p_r < len(num_r):
                if num_l[p_l] <= num_r[p_r]:
                    res.append(num_l[p_l])
                    p_l += 1
                else:
                    res.append(num_r[p_r])
                    p_r += 1
            while p_l < len(num_l):
                res.append(num_l[p_l])
                p_l += 1
            while p_r < len(num_r):
                res.append(num_r[p_r])
                p_r += 1
            p_l, p_r = 0, 0
            while p_l < len(num_l) and p_r < len(num_r):
                if num_l[p_l] <= (num_r[p_r] << 1):
                    p_l += 1
                else:
                    cnt += len(num_l) - p_l
                    p_r += 1
            return res, cnt

        def devision(num_in):
            nonlocal ans
            if len(num_in) == 1:
                return num_in

            num_l = devision(num_in[0: len(num_in) // 2])
            num_r = devision(num_in[len(num_in) // 2: len(num_in) + 1])
            res, cnt = compare(num_l, num_r)
            ans += cnt
            return res

        devision(nums)
        return ans


a = Solution()
nums = list(map(eval, input().split()))
print(a.reversePairs(nums))

注：力扣493题中逆序对要求为标号小的数字标号大的数字的两倍

(四) 快速排序

算法思路

归并即为分治思想，且其中分为很简单的对半操作，而合并较为复杂，为操作

现在考虑一个分较困难，但合简单的算法：每次（随机）选定一个位置数称为主元，分的依据为大于其和小于其的分列两边。重复分下去直至最后，整个排列将有序，合并直接按序合并即可。

最坏复杂度：每次排列完，选定的主元都在最左或最右，这样的总复杂度为

• 特别提示：python3的列表del方法复杂度为，而每次“分”若新建列表，则空间复杂度过大，若要减小空间复杂度，需要直接修改输入的nums数组，选定主轴后维护两个指针，左指针以左是小于主轴的数据，左右指针之间是大于主轴的数据，右指针以右是未和主轴比较的数据。特别注意：类似于C语言，最好维护一个数组的实际长度的变量（py当C用）。

期望复杂度: 通过计算每两个元素间的期望比较次数得到，而

此式的含义为：对于排序结果中序号为、的元素，其发生比较的关键在于：无论每次主轴怎么选取，只有落在中，才能决定这两个元素是否需要比较。若选到或，则发生比较；反之，若未选取到两端的元素，则未发生比较。而选取到以外的数时对这两个元素接下来是否会发生比较没有影响。

(五) 多项式乘法问题

给定两组数与代表两个多项式

求 并将结果以相同形式输出

算法思路

分治法中，有将分为、两组,对应系数也从到记；对b同理，记这两组对应的多项式分别为；则我们要求的即：

而式中的最高指数分别为、、

故我们分治初始时发现递推式为，合并项扫描合并即可，但此算法对应复杂度，与暴力求解相同。

优化：我们发现每一级分治中，最终的可合并，次数同，我们利用未还原系数（即从1开始）的即可得到。

故现在的复杂度为：，最终由主定理，复杂度为

（实际使用更快的趋近于的傅里叶变换）

(六) 第k个最大数问题

问题描述

给定整数数组 和整数，请返回数组中第个最大的元素。最好的算法时间复杂度为

算法思路

• 首先，利用快排的分治思想，每次随机选定一个主轴，主轴一侧为比其小的数（和一半的与其相等的数），另一侧为比其大的数（和另一半相等的数）,每次依据分组结果缩小选定范围。注意这里只需要“分”而不需要"治"，因为输出唯一。

• 另一个思路是建立一个大根堆，每次弹出堆顶的数据，弹出次即为所求的值

复杂度分析

快排的延伸

进一步分析，每种情况概率相同，故：

由于化简至此，由定理无法直接判断，猜测复杂度为，使用代入法进行求解。

设有：

采用等差数列求和公式，提出有

故复杂度为

堆排序的延伸

建立堆的复杂度：建立堆采用自底向上建，可以少遍历底层的复杂度，初始速度从第一个非叶子节点开始()开始，每次保证左右子节点(下表分别为)均小于其，并递归地将换下来的小节点下沉，则第层的最坏情况是，故总复杂度为

设，则式子改写为(调和级数性质？建议错位相减)

故上式结果为，由于 故有总复杂度为

弹出最大数的复杂度：每一次最坏情况，共要弹出次，故最差时间复杂度为，或复杂度为

# https://leetcode.cn/problems/kth-largest-element-in-an-array
# 前者为快排延伸思路，下方为堆的延伸思路
class Solution:
    def findKthLargest(self, nums, k):
        def quick_sort_find():
            left_rank, s_i, e_i = k - 1, 0, len(nums)
            while True:
                if s_i == e_i:
                    return nums[s_i]
                m_i = random.randint(s_i, e_i - 1)
                now_num, p_l, p_r, equal_flag = nums[m_i], s_i, s_i, True
                e_i -= 1
                nums[e_i], nums[m_i] = nums[m_i], nums[e_i]
                while p_r < e_i:
                    if nums[p_r] > now_num:
                        p_r += 1
                    elif nums[p_r] < now_num:
                        nums[p_l], nums[p_r] = nums[p_r], nums[p_l]
                        p_l += 1
                        p_r += 1
                    else:
                        equal_flag = not equal_flag
                        if equal_flag:
                            p_r += 1
                        else:
                            nums[p_l], nums[p_r] = nums[p_r], nums[p_l]
                            p_l += 1
                            p_r += 1
                if p_r - p_l > left_rank:
                    s_i, e_i = p_l, p_r
                elif p_r - p_l < left_rank:
                    e_i = p_l
                    left_rank -= p_r - p_l + 1
                else:
                    return now_num

        #  大根堆 注意维护heap_size
        def heap_solve():
            heap_init()
            heap_size = len(nums)
            for i in range(k):
                heap_pop(heap_size)
                heap_size -= 1
            return nums[heap_size]

        def heap_init():
            for i in range((len(nums) >> 1) - 1, -1, -1):
                shiftDown(i, len(nums))

        def shiftDown(a, heap_size):
            if (a << 1) + 2 < heap_size:
                max_i = (a << 1) + 2 if nums[(a << 1) + 2] > nums[(a << 1) + 1] else (a << 1) + 1
            elif (a << 1) + 1 < heap_size:
                max_i = (a << 1) + 1
            else:
                return
            if nums[max_i] > nums[a]:
                nums[a], nums[max_i] = nums[max_i], nums[a]
                shiftDown(max_i, heap_size)
            return

        def heap_pop(heap_size):
            nums[0], nums[heap_size - 1] = nums[heap_size - 1], nums[0]
            shiftDown(0, heap_size - 1)

        return heap_solve()

(七) 堆排序

参考(六)中建立堆的做法，复杂度

class Solution:
    def sortArray(self, nums):
        heap, heap_l = [i for i in nums], len(nums)

        #  大根堆
        def shiftDown(k):
            while k < heap_l and ((l_c(k) < heap_l and heap[k] < heap[l_c(k)]) or (r_c(k) < heap_l and heap[k] < heap[r_c(k)])):
                if r_c(k) < heap_l and heap[l_c(k)] < heap[r_c(k)]:
                    heap[k], heap[r_c(k)] = heap[r_c(k)], heap[k]
                    k = r_c(k)
                else:
                    heap[k], heap[l_c(k)] = heap[l_c(k)], heap[k]
                    k = l_c(k)

        def l_c(k):
            return (k << 1) + 1

        def r_c(k):
            return (k << 1) + 2

        for i in range((heap_l >> 1), -1, -1):
            shiftDown(i)

        for i in range(len(heap)):
            heap[0], heap[heap_l - 1] = heap[heap_l - 1], heap[0]
            heap_l -= 1
            shiftDown(0)

        return heap

(八) 基于比较排序方法复杂度下限

给定长度为的数组，共有种可能的排列，而每次比较均可以在二叉树中向下一层，故理论最小复杂度为

以下证明：

(九) 计数排序

线性复杂度排序算法 要求数据范围有限

class Solution:    
    def Counting_sort(self, A, k):
        # 创建长度为k的辅助数组C，统计每个整数的出现次数
        B, C = [], []
        for i in range(len(A)):
            B.append(0)
        for i in range(k):
            C.append(0)
        for i in range(len(A)):
            C[A[i] - 1] = C[A[i] - 1] + 1
        # 统计每个数的起始顺序
        for i in range(1, k):
            C[i] += C[i - 1]
        # 打印排序
        for i in range(len(A)):
            B[C[A[i] - 1] - 1] = A[i]
            C[A[i] - 1] -= 1
        return B 

二、动态规划篇

(一) 0-1背包问题

问题描述

有件物品和一个容量为 的背包。第 件物品的重量是 ，价值是 。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入格式：第一行输入, , 后行输入所有物品的

算法思路

动态规划思路：外层循环：遍历每一层物品，对于每种一格空间的情况建立一个（每一格代表剩余一空间的情况)

则关键的状态转移方程为:

因此，可以倒序每次倒序遍历，由大至小直至下标到为止。每次更新的值，共更新次

初态：全部置0即可

//https://www.luogu.com.cn/problem/P2871
#include <stdio.h>

int main() {
    int M, N;
    int i, wi, ci, j;
    int items[5000][2] = {{0}};
    scanf("%d %d", &N, &M);
    for(i = 0; i < N; i++){
        scanf("%d %d", &ci, &wi);
        items[i][0] = ci, items[i][1] = wi;
    }

    int dp[13000] = {0};
    for (i = 1; i <= N; i++) {
        for (j = M; j >= items[i-1][0]; j--) {
            if (j - items[i-1][0] >= 0 && dp[j - items[i-1][0]] + items[i-1][1] > dp[j]) {
                dp[j] = dp[j - items[i-1][0]] + items[i-1][1];
            }
        }
    }
    printf("%d", dp[M]);
    return 0;
}

(二) 最大子数组问题-ii

注意：子数组/子串为连续，子序列可以不连续，前者一般，后者一般(不加奇奇怪怪优化的情况下)

详见前第一章(二)中解法，

状态转移方程（固定结束点）：

其中为以下标的数字为末尾的子数组最大和。

我们也可以固定起始点，倒序遍历列出状态转移方程：

最后加上滚动数组优化，空间复杂度，时间复杂度。

(三) 最长公共子序列问题

问题描述

给定两个字符串 和 ，返回这两个字符串的最长公共子序列的长度。如果不存在 公共子序列，返回 0 。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

算法思路

考虑一个二维表，其中代表与最长公共子序列的长度

现在考虑状态转移方程：

如果，则考虑这两个字母挖去以后再加上新增的相同字母，故

而若果, 则最长子序列应该产生在：取最后一个字母但不取最后一个字母，反之取而不取，或者最后一个字母都不取。总之这两个末尾字母不会同时出现在子序列，因为出现则必为最后一个字母，两者必须相等，与假设矛盾。

故

总的状态转移方程，最终所求为:

加上滚动数组优化，最终时间复杂度，空间复杂度

实际开数组时，多开一格表示长度为时的最长子序列，值为

# https://leetcode.cn/problems/longest-common-subsequence
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [0 for _ in range(len(text1)+1)]
        for i in range(len(text2)):
            tmp = [0 for _ in range(len(text1) + 1)]
            for j in range(1, len(text1)+1):
                tmp[j] = dp[j-1] + 1 if text2[i] == text1[j-1] else max(dp[j], tmp[j-1])
            dp = tmp
        return dp[-1]

(四) 最长公共子串问题

问题描述

给定两个字符串 和 ，返回这两个字符串的最长公共子串的长度。如果不存在公共子串，返回 0 。

子串要求连续。

算法思路

基本同上题，不同的是，由于子串必须连续，故时，我们有

故状态转移方程，最终所求为：

# https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
class Solution:    
    def findLength(self, nums1: list[int], nums2: list[int]) -> int:
        dp = [[0 for _ in range(len(nums2))] for __ in range(len(nums1))]
        ans = 0
        for i in range(len(nums1)):
            for j in range(len(nums2)):
                if nums1[i] == nums2[j]:
                    dp[i][j] = dp[i-1][j-1] + 1 if i != 0 and j != 0 else 1
                    ans = max(ans, dp[i][j])
                else:
                    dp[i][j] = 0
        return ans

(五) 编辑距离问题

问题描述

给你两个单词和,请返回将 转换成 所使用的最少操作数 。

你可以对一个单词进行三种操作：插入一个字符、删除一个字符、替换一个字符

算法思路

我们同样考虑二维矩阵，其中即代表和间的距离。对于两个单词，首先不难发现插入和删除字符是镜像操作，即1转2和2转1应该有相同的最小操作数。我们接下来不妨设考虑转换,进行三种不同操作：

接下来递推地讨论子结构，如果对最后一个字符进行删除，则还需要次操作，共需要次操作，如果增加，则最优加法为增加这个字符，还需要次操作，共需要次操作。如果替换，同样最有操作为将字符替换为字符，则需要次的操作,而两者相同时，只需要次的操作。

故综上，状态转移方程为：

可以利用滚动数组进行优化。

# https://leetcode.cn/problems/edit-distance
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [i for i in range(len(word1) + 1)]
        for i in range(len(word2)):
            tmp = [0 for _ in range(len(word1) + 1)]
            tmp[0] = i + 1
            for j in range(1, len(word1)+1):
                tmp[j] = dp[j-1] if word2[i] == word1[j-1] else min(tmp[j-1], dp[j], dp[j-1]) + 1
            dp = tmp
        return dp[-1]

(六) 钢条切割

问题描述

现有一段长度为10的钢条，可以零成本将其切割为多段长度更小钢条，且不同长度价格不同，，价格如表C，问如何切割收益最大？

算法思路

每个长度的钢条切割后，都变为更短长度切割的相同子问题，具有相同的最优子结构。

故写出dp方程：

复杂度为

(七) 矩阵乘法加括号问题

咕了

三、贪心算法

(一) 部分背包问题

(二) Huffman编码

以上两问题，咕

(三)活动选择问题

如果不带权重，优先选择结束早的活动，腾挪出更大的空间。复杂度O(nlogn)，瓶颈在排序

如果带权重，采用动态规划思想，最优子问题为1-n个活动中1-i个的最大权（前不影响后），记为dp[i]

其中prev为第i个活动开始前最后结束活动的序号。复杂度O(nlogn)，瓶颈在排序和为每个活动二分查找其开始前最后结束的活动

四、图算法

图的BFS

• 复杂度 O(V+E)
• 应用

无向无权图最短路

拓扑排序（入队点为入度0的点）

图的DFS及其附属产品

• 复杂度 O(V+E)

• 图的环路存在性判断：有无后向边

• 拓扑排序：dfs输出顺序逆序即可

• 强联通分量求解：按反向DFS出队顺序，在原图反向重跑DFS

单源点最短路径 Dijkstra及BellmanFord算法

堆优化的迪杰特斯拉算法：复杂度

BellmanFord：松弛V次全部边，复杂度

注：稠密图中，也可认为是

全图最短路径 Floyd算法

结合动态规划思想处理重叠子问题

三维dp,为：各个点间至多经过前k个点的最短路

dp公式：

复杂度

匹配问题 匈牙利算法

核心思想：寻找增广路径增加匹配数

辅助数组：每轮重置，用于递归查找，复杂度

复杂度

五、NP难问题

(一) P问题和NP问题

1 问题的输入规模

问题的输入规模取决于最小的编码问题输入的二进制字符数

2 决策问题和优化问题

• 决策问题 —— 问题答案为yes或no
• 优化问题 —— 给出优化策略
• 决策问题及相关的优化问题

MST 最小生成树 DST 决策生成树

Knapsack 背包问题 Decision Knapsack 决策背包

• yes-input：对于决策问题而言，应给出yes答案的输入
• no-input： 同上2，应给出no答案

3 P和NP问题

P问题

指决策问题，其次，是多项式时间内可解决的决策问题

常见P问题

判断给定的图是否是树 （DFS无后向边，O(V+E)）

DST问题（给定带权图，是否有小于某个值的生成树） (克鲁斯卡尔，O((V+E)logn))

NP问题

指决策问题，且是给定yes-输入，多项式时间内可验证是yes-输入的决策问题

判断合数问题(yes 输入是一个因数)

整数集有无子集和为某数问题（yes 输入就是子集）

DVC问题（分割成二部图）（yes 输入是一个分割）

SAT问题（合取范式是否可为真问题） （yes输入即为变量布尔值）

3-SAT问题(析取式均有3个变量)

两者关系

P问题都是NP问题（多项式可解则必可验证）

而P=NP？未定论

4 NPC 问题

粗略定义：“最难的”NP问题

SAT问题 NPC

CLIQUE问题（最大完全图子图问题） NPC 注：此即“团”，寻找最大团问题才为NPC

图的最大独立集问题 NPC

背包问题 NPC

5 NP-hard 问题

粗略定义：每个NPC问题对应的优化问题即为NP难问题