【算法设计与分析】期末考试复习 - 基础知识（基础知识超详细）

文章目录

前言
引言问题
- 问题描述
- 实例
- 目标
- - 数学表达
  - 步骤
  - 示例
  - - 伪代码
    - 解释
1. 问题的复杂度
2. 计算复杂性理论
3.算法以及时间复杂度
4.算法的伪代码表示
5. 函数渐进的界
6.有关函数渐进的界的定理
递归树
参考文献
写在最后
END

前言

本系列课程总共详细讲解基础知识、分治、动态规划、贪心、回溯

本文为讲解基础知识

引言问题

问题描述

$m$ 万元钱，投资 $n$ 个项目，效益函数 $f_i(x)$ 表示第 $i$ 个项目投 $x$ 元的效益， $\ldots , n$ 。求如何分配每个项目的钱使得总效益最大？

实例

投资金额：5万元
投资项目数：4个项目

效益函数如下表所示：

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	0	0
1	11	0	2	20
2	12	5	10	21
3	13	10	30	22
4	14	15	32	23
5	15	20	40	24

目标

找出分配给每个项目的钱，使得总效益最大。

数学表达

目标函数： $\max \sum_{i=1}^{n} f_i(x_i)$

约束条件：

$\sum_{i=1}^{n} x_i \leq m$
$x_i \geq 0$

其中， $x_i$ 表示分配给第 $i$ 个项目的资金。

思想：蛮力算法是一种通过穷举所有可能的方案，找到最佳解的方法。

对于这个问题，我们需要穷举所有可能的资金分配方式，然后计算每种分配方式下的总效益，选择总效益最大的分配方式。具体步骤如下：
在这里插入图片描述

步骤

枚举所有可能的资金分配方案：
- 假设我们有 $m$ 万元钱和 $n$ 个项目，则我们需要枚举每个项目可以分配的资金 $x_i$ ，满足约束条件 $\sum_{i=1}^{n} x_i \leq m$ 。
- 每个项目的资金可以从0到 $m$ 的整数值。
计算每种分配方案的总效益：
- 对于每种分配方案 $\{x_1, x_2, \ldots, x_n\}$ ，计算其总效益 $\sum_{i=1}^{n} f_i(x_i)$ 。
选择总效益最大的分配方案：
- 在所有枚举的分配方案中，选择总效益最大的那一个。

示例

以实例中的数据为例（ $m = 5$ 万元， $n = 4$ 个项目），我们将枚举每个项目从0到5的资金分配方式。

伪代码

def brute_force_max_profit(m, n, profit_functions):
    max_profit = 0
    best_allocation = None
    
    # 枚举所有可能的分配方式（不优雅的写法）
    for x1 in range(m + 1):
        for x2 in range(m + 1):
            for x3 in range(m + 1):
                for x4 in range(m + 1):
                    if x1 + x2 + x3 + x4 <= m:  # 确保总投资不超过m万元
                        total_profit = profit_functions[0][x1] + profit_functions[1][x2] + profit_functions[2][x3] + profit_functions[3][x4]
                        if total_profit > max_profit:
                            max_profit = total_profit
                            best_allocation = (x1, x2, x3, x4)
    
    return max_profit, best_allocation


profit_functions = [
    [0, 11, 12, 13, 14, 15],  # f1(x)
    [0, 0, 5, 10, 15, 20],    # f2(x)
    [0, 2, 10, 30, 32, 40],   # f3(x)
    [0, 20, 21, 22, 23, 24]   # f4(x)
]

m = 5
n = 4

max_profit, best_allocation = brute_force_max_profit(m, n, profit_functions)
print(f"最大总效益: {max_profit}, 最佳分配方式: {best_allocation}")

这代码不够优雅

解释

我们有四个嵌套的循环，每个循环从0到 $m$ （即5）。
通过嵌套循环枚举所有可能的分配方式，并检查总投资是否不超过 $m$ 万元。
计算每种分配方式下的总效益，并记录最大效益及对应的分配方式。

显然这种思路比较好想，但是时间复杂度比较高，大规模不适用

拉莫有没有更好的方法呢，首先我们看一个刚才这里提到的概念 - 问题的复杂度

1. 问题的复杂度

算法类别	算法	最好时间复杂度	最坏时间复杂度	最好空间复杂度	最坏空间复杂度
排序算法	冒泡排序	O(n)	O(n^2)	O(1)	O(1)
排序算法	选择排序	O(n^2)	O(n^2)	O(1)	O(1)
排序算法	插入排序	O(n)	O(n^2)	O(1)	O(1)
排序算法	归并排序	O(n log n)	O(n log n)	O(n)	O(n)
排序算法	快速排序	O(n log n)	O(n^2)	O(log n)	O(log n)
排序算法	堆排序	O(n log n)	O(n log n)	O(1)	O(1)
排序算法	桶排序	O(n)	O(n^2)	O(n)	O(n)
排序算法	计数排序	O(n + k)	O(n + k)	O(k)	O(k)
排序算法	基数排序	O(nk)	O(nk)	O(n + k)	O(n + k)
搜索算法	二分查找	O(1)	O(log n)	O(1)	O(1)
动态规划	斐波那契数	O(1)	O(n)	O(1)	O(n)
图算法	Dijkstra	O(E + V log V)	O(E + V log V)	O(V)	O(V)
图算法	Floyd-Warshall	O(V^3)	O(V^3)	O(V^2)	O(V^2)
图算法	Prim	O(E log V)	O(E log V)	O(V)	O(V)
图算法	Kruskal	O(E log E)	O(E log E)	O(V)	O(V)
图算法	Bellman-Ford	O(EV)	O(EV)	O(V)	O(V)
查找算法	哈希查找	O(1)	O(n)	O(n)	O(n)
字符串算法	KMP	O(m + n)	O(m + n)	O(m)	O(m)
字符串算法	Rabin-Karp	O(m + n)	O(mn)	O(1)	O(1)

注：n表示输入数据的规模，k表示数据范围，m表示模式串的长度，E表示边的数量，V表示顶点的数量。

首先来理解各个排序算法

冒泡排序笔记

核心原理：
冒泡排序是一种简单的排序算法。它重复地遍历要排序的列表，比较相邻的两个元素，如果它们的顺序错误就交换它们的位置。这个过程重复进行，直到没有需要交换的元素为止。其名字来源于算法中较大的元素会逐渐“冒泡”到列表的顶端。

实际上也有点这样的意思，就是选定当前元素为某点，然后比较下一个元素和当前元素的大小。如果下一个元素比当前元素大的话。那么就把当前的某点放到这个比当前元素大的这个元素，那么某点到了下一个元素，然后继续比较。这是第1种情况，然后第2种情况的话就是，如果下一个元素比当前元素小的话，就把这两个替换。
在这里插入图片描述
总之每次都是使得较为大的元素向后

时间复杂度：

最好情况： O(n) （扫描一遍过去即可）
- 最好情况下，列表已经是有序的。在这种情况下，冒泡排序只需要进行一次遍历来确认列表已经有序，不需要进行任何交换。因此，时间复杂度为O(n)。
平均情况： O(n^2)
- 平均情况下，列表中的元素是随机排列的。冒泡排序需要进行n次遍历，每次遍历需要进行(n-1)次比较。平均情况下，每次比较可能需要进行交换，所以时间复杂度为O(n^2)。(这里实际上用趟来解释更好，每次操作一个元素冒泡，一个元素一趟，每趟需要比较大概n次，因为有N个元素，所以需要n趟)
最坏情况： O(n^2)
- 最坏情况下，列表是逆序的。在这种情况下，冒泡排序需要进行n次遍历，每次遍历需要进行(n-1)次比较和交换。因此，时间复杂度为O(n^2)。

空间复杂度：
冒泡排序是一种原地排序算法，只需要常数级别的额外空间。除了用于交换的临时变量外，不需要额外的存储空间。因此，空间复杂度为O(1)。

选择排序笔记

核心原理：
选择排序是一种简单直观的排序算法。其基本思想是：首先从待排序的列表中找到最小（最大）元素，放到序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（最大）元素，放到已排序序列（注意是已经排序的序列）的末尾。如此循环，直到所有元素均排序完毕。
在这里插入图片描述
小的放到前面就是

这里注意，放到有序去里面采用的方式是无序区里面的（假设找小放前面为例子）最靠近有序的那个元素与当前选定的最小的元素交换

在这里插入图片描述

时间复杂度：

最好情况： O(n^2)
- 在选择排序中，不论初始数组是否有序，每一轮都要扫描未排序的部分来找到最小（或最大）元素。因此，每一轮都需要进行n-i次比较（i是当前轮次）。即使数组已经有序，仍然需要进行这些比较。因此，最好情况下时间复杂度仍然是O(n^2)。
平均情况： O(n^2)
- 平均情况下，选择排序的操作步骤和最好情况完全相同，每轮都需要进行n-i次比较。因此，平均情况下时间复杂度为O(n^2)。
最坏情况： O(n^2)
- 在最坏情况下，选择排序同样需要进行固定次数的比较操作。因此，不论数组初始状态如何，选择排序每一轮都需要进行n-i次比较。因此，最坏情况下时间复杂度为O(n^2)。

空间复杂度：
选择排序是一种原地排序算法，只需要常数级别的额外空间。除了用于交换的临时变量外，不需要额外的存储空间。因此，空间复杂度为O(1)。

插入排序笔记

核心原理：
插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

时间复杂度：

最好情况： O(n)
- 最好情况下，列表已经是有序的。在这种情况下，每次插入操作只需要比较一次就可以确定元素的位置，不需要进行移动。因此，时间复杂度为O(n)。（就是每次都确定当前新拿到的元素就是已经放置好的位置，然后一遍扫描过去）
平均情况： O(n^2)
- 平均情况下，列表中的元素是随机排列的。插入排序需要对每个元素进行插入操作，插入操作平均需要比较和移动n/2次。由于有n个元素，因此时间复杂度为O(n^2)。
最坏情况： O(n^2)
- 最坏情况下，列表是逆序的。在这种情况下，每次插入操作都需要比较和移动所有之前的元素。插入排序需要进行n次插入操作，每次插入操作需要比较和移动n-1次。因此，时间复杂度为O(n^2)。

空间复杂度：
插入排序是一种原地排序算法，只需要常数级别的额外空间。除了用于交换的临时变量外，不需要额外的存储空间。因此，空间复杂度为O(1)。

上面的都是时间复杂度比较大的，下面看几个优化时间复杂度的

归并排序笔记

核心原理：
归并排序是一种分治算法。其基本思想是将数组分成两半，分别对每一半进行排序，然后将两部分合并成一个有序数组。这一过程递归进行，直到每部分的规模为1（此时视为已排序），然后逐层向上合并，最终形成一个完整的有序数组。
在这里插入图片描述

时间复杂度：

最好情况： O(n log n)
- 在最好情况下，归并排序的每一步都需要进行对半拆分和合并操作。拆分的复杂度为O(log n)，每一层的合并操作复杂度为O(n)，因此总的时间复杂度为O(n log n)。
平均情况： O(n log n)
- 平均情况下，归并排序的操作步骤和最好情况完全相同，不受输入数据的初始排列状态影响。每一层都需要进行O(n)的合并操作，共有O(log n)层，因此时间复杂度为O(n log n)。
最坏情况： O(n log n)
- 在最坏情况下，归并排序仍然需要进行相同次数的拆分和合并操作，时间复杂度为O(n log n)。输入数据的初始状态不会影响归并排序的基本操作步骤。

空间复杂度：
归并排序不是原地排序算法，因为它需要额外的存储空间来保存拆分后的子数组和合并时的临时数组。空间复杂度为O(n)，其中n是数组的大小。这是因为在合并过程中需要额外的O(n)空间来临时存储排序结果。

快速排序笔记

核心原理：
快速排序是一种分治算法，通过选择一个基准元素（通常是数组中的第一个元素），将数组分成两部分：小于基准元素的部分和大于基准元素的部分。然后递归地对这两部分进行排序，直到整个数组有序。

时间复杂度：

树的高度 logn 然后每一层由于两个指针相当于每个元素检查了一遍，n
所以最终nlogn

最好情况： O(n log n)
- 在最好情况下，每次划分都能平均地把数组分成大小大致相等的两部分。因此，快速排序的递归深度为O(log n)，每层需要O(n)的时间来进行划分操作。因此，总的时间复杂度为O(n log n)。
平均情况： O(n log n)
- 平均情况下，快速排序能够保持每次划分都能将数组分成大小相近的两部分，递归深度为O(log n)，每层需要O(n)的时间来进行划分操作。因此，平均时间复杂度为O(n log n)。
最坏情况： O(n^2)
- 在最坏情况下，每次划分只能将数组分成大小为n-1和0的两部分。这种情况通常发生在数组已经有序或者逆序的情况下。此时快速排序的递归深度为O(n)，每层需要O(n)的时间来进行划分操作。因此，最坏情况下时间复杂度为O( $n^2$ )。
  （n*n）

空间复杂度：
快速排序通常是原地排序，只需要常数级别的额外空间用于递归调用时的栈空间。因此，空间复杂度为O(log n)。

在这里插入图片描述
注意一种特殊情况（每次都是这种也就是最坏情况，树结构直接退化为链表）

另外这个最小的叶子终止条件是，序列长度为0或者1，这种情况和归并一样的，一个元素自然有序，随后返回向上（向父节点）

举个例子
在这里插入图片描述

一些问题

哪个排序算法效率最高？

1. 常见排序算法及其效率：

快速排序 (Quicksort)：
- 平均时间复杂度：(O(n \log n))
- 最坏时间复杂度：(O(n^2))（可以通过随机化枢轴选择降低）
- 空间复杂度：(O(\log n))
- 通常是实际应用中最快的比较排序算法之一。
归并排序 (Mergesort)：
- 时间复杂度：(O(n \log n))
- 空间复杂度：(O(n))
- 稳定排序，适用于大数据集。
堆排序 (Heapsort)：
- 时间复杂度：(O(n \log n))
- 空间复杂度：(O(1))
- 不稳定排序，但在内存有限时表现出色。
计数排序 (Counting Sort)：
- 时间复杂度：(O(n + k))，其中 (k) 是数据范围
- 空间复杂度：(O(k))
- 适用于数据范围较小的整数排序，且是稳定排序。
桶排序 (Bucket Sort)：
- 时间复杂度：平均为 (O(n + k))，其中 (k) 是桶的数量
- 空间复杂度：(O(n + k))
- 在输入数据均匀分布时表现优异。
基数排序 (Radix Sort)：
- 时间复杂度：(O(d(n + k)))，其中 (d) 是数字的位数，(k) 是基数
- 空间复杂度：(O(n + k))
- 适用于整数或字符串的排序，且是稳定排序。

是否可以找到更好的排序算法？

比较排序算法的下界：
对于基于比较的排序算法，其最坏情况下的时间复杂度下界是 (O(n \log n))。这是通过比较树的高度得出的，因为对 (n) 个元素的排序可以看作是二叉决策树，每个内部节点是一次比较操作。

非比较排序算法：
在某些特定情况下，可以找到时间复杂度低于 (O(n \log n)) 的排序算法，例如：

计数排序、桶排序和基数排序在特定情况下可以达到线性时间复杂度 (O(n))。

排序问题计算难度如何？

排序问题是计算机科学中的一个经典问题，通常被认为是“简单”的问题，因为有很多有效的算法来解决它。排序问题属于 P 类问题（可以在多项式时间内解决的问题）。

其他排序算法的复杂度

以下是一些其他常见排序算法及其复杂度：

插入排序 (Insertion Sort)：
- 时间复杂度：(O(n^2))
- 最好情况下：(O(n))（对于几乎有序的数组）
- 空间复杂度：(O(1))
- 稳定排序，适用于小规模数据集或几乎有序的数组。
选择排序 (Selection Sort)：
- 时间复杂度：(O(n^2))
- 空间复杂度：(O(1))
- 不稳定排序，但实现简单。
冒泡排序 (Bubble Sort)：
- 时间复杂度：(O(n^2))
- 最好情况下：(O(n))（对于几乎有序的数组）
- 空间复杂度：(O(1))
- 稳定排序，但效率较低。

问题计算复杂度估计方法

计算复杂度估计方法主要有以下几种：

渐近分析 (Asymptotic Analysis)：
- 主要使用大 O 符号来表示时间和空间复杂度，描述输入规模趋向无穷时算法的增长速度。
最坏情况分析 (Worst-case Analysis)：
- 评估算法在最不利情况下的性能。
平均情况分析 (Average-case Analysis)：
- 评估算法在所有可能输入的平均性能。
最优情况分析 (Best-case Analysis)：
- 评估算法在最有利情况下的性能。
摊销分析 (Amortized Analysis)：
- 用于分析一系列操作的平均时间复杂度，特别是在某些操作很快而其他操作很慢的情况下。例如，动态数组扩展的摊销分析。