第一章—算法：

        「1」定义：若干条指令组成的有穷序列

        「2」性质：

                （1）输入：有零个或多个由外部提供的量作为算法的输入

                （2）输出：算法至少有一个输出

                （3）确定性：组成算法的每条指令都是清晰的，无歧义的

                （4）有限性：算法中每条指令的执行次数都是有限的，执行每条指令的时间也是有限的。

        「3」算法复杂性：（时间复杂度 + 空间复杂度）【一般指考虑最坏、平均、最好三种情况】

                （1）时间复杂度：利用某一算法处理一个问题规模为n的输入所需的时间，称为该算法的时间复杂性。记为 T ( n ) 

                （2）近似时间复杂度：原有的时间复杂度只保留高级无穷量即可。（O的定义）

                        【详细的定义可以查一下，一般只考高阶定义和使用。】

                        例子：3N = O（N）； + N = O()

        「4」延展（程序）：【  程序 = 算法 + 数据结构】 程序可以不满足有限性（因为程序可以无休止的运行）

        【🐑注：你可以理解成，你可以任何时候访问奶茶小程序，因为这个程序不停止】  

第二章—递归与分治：

（一）递归：直接或间接的调用自身的算法。（同理得递归函数的定义）

        （1）递归必须要包含的两个因素：

•         边界条件：结束算法（保证算法的有限性）

  • 递归方程：如何把原来的算法用递归方法表示

        （2）实例

                1）阶乘函数：

                        

                时间复杂度为O（N）

                2）斐波那契数列：第三项开始的第n项值是前两项之和。（n = 0开始）

                        

                时间复杂度为

                3）汉诺塔函数

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi(n-1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n-1, auxiliary, target, source)

# 示例：移动3个盘子，从柱子A到柱子C，使用柱子B作为辅助
hanoi(3, 'A', 'C', 'B')
 

                4)Ackerman函数

                5）排列问题

                6）整数划分

（二）分治法

        （1）基本思想：将一个规模为n的问题分解成k个规模较小的子问题，这些子问题互相独立且与原问题相同，递归解决这些子问题，然后将各子问题的解合并成为原解。

        （2）使用情况：

                1）能使子问题的规模大致相同

                2）规模缩小到一定程度可以解决

                3）分解成的子问题的解能够合并成该问题的解

                4）各个子问题之间相互独立，且子问题不包含公共子问题

        （3）三步骤：

                1）分解

                2）计算

                3）合并

         （4）计算时间公式的推导

                        

             推导过程：展开了N次，就能够得到 N = log n/ log m, 就相当于有N 个 k 相乘 ，然后拆分合并

                        

        （5）实例

                1）二分搜索技术：给定排好序的n个元素，找出一个特定元素x（平时是顺序查找）

def first_occurrence(arr, target):
    low, high, result = 0, len(arr) - 1, -1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] >= target:
            high = mid - 1
            if arr[mid] == target:
                result = mid
        else:
            low = mid + 1
    return result
 

                时间复杂度：O（logn）

                2）Strassen矩阵

                        传统的思路：

                        

                        

                        分治法的思路：

                        

                时间复杂度：O()

                3）快速排序（整体感觉有点像是二分搜索的变形体）O（n log n）

              4）合并排序（整体来说会更加麻烦）O（n log n）

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

    return arr
 

第三章—动态规划：

（1）基本思想 + VS 分治法

        1）基本思想：将待求解问题分解成若干个子问题，先求解子问题，在结合子问题的解得到原问题的解，并用一个表来记录所有已解决的子问题的答案。

        2）VS分治法：

                1.动态规划得到的子问题之间往往不是相互独立的（不使用分治法）

                2.动态规划的子问题的结果不会被重复计算（分治法需要重复计算多次）

（2）基本要素：

        1）最优子结构：

        【当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质】

        2）重叠子问题：

        【在采用递归进行计算时，每次产生的子问题并不总是新问题，有一些问题需要被重复计算】

（3）步骤：

        1）找出最优解性质，并刻画其结构特征

        2）递归定义最优值

        3）以自底向上的方式计算最优值

        4）根据计算最优值时得到的信息，构造最优解

（4）实例：

        1）矩阵连乘

                给定一组矩阵 A₁, A₂, ..., Aₙ，要确定它们的乘法顺序，使得总的标量乘法次数最少。

•         矩阵乘法是有结合性的，但不同的加括号顺序，其计算代价不同。

  • 比如：

    A(10×100), B(100×5), C(5×50) 计算顺序 (A·B)·C 和 A·(B·C) 的乘法次数就不同。

                1. 状态定义：

                ​​​​​​​        ​​​​​​​        

•         m[i][k] 表示前一段乘法的最优代价；

  •      m[k+1][j] 表示后一段乘法的最优代价；

         p_{i-1} * p_k * p_j 是合并两个结果矩阵的乘法代价。

        2）最长公共子序列

                1.若给定序列X={x1,x2,…,x m}，则另一序列Z={z 1,z2,…,z k }，是X的子序列是指存在一个严格递增下标序列{i 1,i 2,…,i k }使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。

                给定序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是X和Y的公共子序列。

                2.定理：(一个LCS的最优子结构)
                设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为 Z={z1,z2,…,zk} ，则
                (1)若xm=yn，则zk=xm=yn，且Zk-1是X m-1和Y n-1的最长公共子序列。
                (2)若xm≠yn且zk≠xm，则Z是X m-1和Y的最长公共子序列。
                (3)若xm≠yn且zk≠yn，则Z是X和Y n-1的最长公共子序列

                3.子问题的递归结构
                • 将X和Y的LCS分解为2种情况：
                        – 如x m =y n，找Xm-1和Yn-1的LCS；
                        – 如x m ≠y n，找Xm-1和Y的LCS；
                        找X和Yn-1的LCS；
                        取两者中的最大的；

                现在有序列X：ABCB，Y：BDCAB，可以一步步推导得到：

                        

        最终答案：dp[4][5] = 3，也就是最优子序列为BCB