起泡排序





[https://www.bilibili.com/video/av49361421?p=75](https://www.bilibili.com/video/av49361421?p=75)

初始版本时间复杂度O（n^2）。

改进：考虑到向量中的前段和后段是不是已经是有序的。前段有的话就不再继续排序，后段有的话就把hi点放到前段最大值那里。

![在这里插入图片描述](/static/img/images/02519.png)

算法是否稳定？

![在这里插入图片描述](/static/img/images/02520.png)

归并排序

[https://www.bilibili.com/video/av18980253/](https://www.bilibili.com/video/av18980253/)

时间复杂度O（nlogn）。

先分，再merge归并。分而治之的算法。

![在这里插入图片描述](/static/img/images/02521.png)

C代码实现：

```c
#include <stdio.h>
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}
void merge_sort(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}
int main() {
    int a[]={1,2,3,3,2,4,5,6,7,8,3,4,5,6,22,33,44,22,11};
    int i= 19;
    merge_sort(a, i);
    while(i--)
        printf("%d    ",a[i]);
    return 0;
}
```

[数据结构与算法] 排序算法 起泡排序 归并排序

最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经典的计算机科学问题，也是数据比较程序，比如Diff工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变。






使用递归解决LCS问题

[https://www.bilibili.com/video/av49361421?p=30](https://www.bilibili.com/video/av49361421?p=30)

![在这里插入图片描述](/static/img/images/02522.png)

![在这里插入图片描述](/static/img/images/02523.png)

![在这里插入图片描述](/static/img/images/02524.png)

python实现

```python
def lcs_dp(input_x, input_y):
    # input_y as column, input_x as row
    dp = [([0] * (len(input_y) + 1)) for i in range(len(input_x) + 1)]
    for i in range(1, len(input_x) + 1):
        for j in range(1, len(input_y) + 1):
            if input_x[i - 1] == input_y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1  # 这是一个规律 必定是左上角数字加1
            else:  # 不相等
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # 这是一个规律 必定是左边或者上面最大的数字
    for dp_line in dp:
        print(dp_line)
    return dp[-1][-1]
x = list("412387ty")
y = list("g123ZX6789yt")
print(lcs_dp(x, y))
```

上面的代码的结果如下图，代码主要依据了2个规律给了矩阵。

![在这里插入图片描述](/static/img/images/02525.png)

对于给的x和y（x = list("412387ty")

y = list("g123ZX6789yt")）

这个最长公共子序列的解是多解的，如何给出所有符合的字符串？

下面代码给出了答案。

程序里加了一个subdp这样这个二维数组用于保存子序列。在矩阵从左到右从上到下这样一个Z字的更新过程中，在遇到相同点的时候：如果是新出来的节点，subdp这个二维列表在是直接在每一行（代表一个最长公共子序列）的最后面append此时相等的元素；如果是一样长的节点（多解），subdp这个二维列表会深度复制目前查找到的所有最长公共子序列，修改最后一个元素为此时相等的元素，然后作为新路径存入subdp。

```python
import copy
def lcs_dp(input_x, input_y):
    # input_y as column, input_x as row
    dp = [([0] * (len(input_y) + 1)) for i in range(len(input_x) + 1)]
    num = 0
    subdp = [[]]
    subdp_temp=[]
    for i in range(1, len(input_x) + 1):
        for j in range(1, len(input_y) + 1):
            if input_x[i - 1] == input_y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1  # 这是一个规律 必定是左上角数字加1
                if num >= dp[i][j]:
                    # 这里的点是再次遇到一样的分支
                    for dp_i in range(len(subdp)):
                        subdp_temp=copy.deepcopy(subdp[dp_i])
                        subdp_temp[-1]=input_x[i - 1]
                        subdp.append(subdp_temp)
                else:
                    for dp_i in range(len(subdp)):
                        subdp[dp_i].append(input_x[i - 1])
                num = dp[i][j]
            else:  # 不相等
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # 这是一个规律 必定是左边或者上面最大的数字
    for dp_line in dp:
        print(dp_line)
    return dp[-1][-1], subdp
x = list("412387tyuu")
y = list("g123ZX6789ytopopop")
print(lcs_dp(x, y))
```

结果如下图

![在这里插入图片描述](/static/img/images/02526.png)

[数据结构与算法] 最长公共子序列 LCS问题 python

# 0 写在前面





递归就是将一个问题以“减而治之”的思想分解为一个平凡数和另外一个规模缩小的子问题，另外一个子问题也可以用相似想法继续分解下去。或者说，递归就是将一个问题以“分而治之”的思想分解为一个规模缩小的子问题和另外一个规模缩小的子问题，两个规模缩小的子问题也可以用相似想法继续分解下去。

递归是好东西，但是对于大规模问题，递归的设计非常重要，不然就会造成巨大问题。可以使用递归跟踪（recursion trace）或者递归方程去分析递归算法的效率。

如果一个问题可以递归解决、也可以用迭代解决，鉴于递归这么烦人的特性（难设计好），优先用迭代解决问题。


# 1 为什么推荐迭代法解决问题？

参考邓军辉老师的数据结构与算法C++版本的书籍。

以前上课，老师很推荐递归，以前有句话叫“`迭代乃人工，递归方神通`”，因为递归出来的一切都是程序自己调用自己负责的，突显了程序的智能特性。但可能现在我们得推荐`由递归转向迭代` 。

> 递归也是一种基本而典型的算法设计模式。这一模式可以对实际问题中反复出现的结构和形

> 式做高度概括，并从本质层面加以描述与刻画，进而导出高效的算法。从程序结构的角度看，递

> 归模式能够统筹纷繁多变的具体情况，避免复杂的分支以及嵌套的循环，从而更为简明地描述和

> 实现算法，减少代码量，提高算法的可读性，保证算法的整体效率。

`递归很容易造成空间浪费和效率不行`，学习了数据结构与算法这门课，就得学会去分析问题：一般地，能用迭代方法解决问题的，就尽量想出一个迭代的方法，而不要使用递归，因为递归太难设计妥当。

> 从递归跟踪分析的角度不难看出，递归算法所消耗的空间量主要取决于递归深度（习

> 题[1-17]），故较之同一算法的迭代版，递归版往往需耗费更多空间，并进而影响实际的运行

> 速度。另外，就操作系统而言，为实现递归调用需要花费大量额外的时间以创建、维护和销毁各

> 递归实例，这些也会令计算的负担雪上加霜。有鉴于此，在对运行速度要求极高、存储空间需精 

> 打细算的场合，往往应将递归算法改写成等价的非递归版本。


# 2 什么是递归？

斐波那契数列的通项公式是：

![在这里插入图片描述](/static/img/images/02531.png)

下面就是一个设计得很糟糕的递归算法：

```c
__int64 fib(int n)
{
    return (2 > n) ? (__int64)n : fib(n - 1) + fib(n - 2);
}
```

如果调用fib(10)，程序会计算fib(9)和fib(8)，然后计算fib(8)和fib(7)、fib(7)和fib(6)……

可见程序会重复计算一些之前已经计算过的数值，当问题规模变大时，比如求fib(100)，运行O(2^n)时间时间才能计算完毕，而且巨大地浪费内存，这违背高效率准则。

# 3 递归的形式

递归在有的情况里，还是非常经典的。并不是递归不好，而是递归的设计更难（如果你想要高效率）。

`递归的形式有：线性递归、二分递归和多分支递归等` 

## 3.1 线性递归求数组的前n项和
```c
//线性递归
int sum(int A[], int n)
{
    if (1 > n)
        return 0;
    else
        return sum(A, n - 1) + A[n - 1];
}
```

> 线性递归的模式，往往对应于所谓`减而治之`（decrease-and-conquer）的算法策略：递归

> 每深入一层，待求解问题的规模都缩减一个常数，直至最终蜕化为平凡的小（简单）问题。

> 按照减而治之策略，此处随着递归的深入，调用参数将单调地线性递减。因此无论最初输入

> 的n有多大，递归调用的总次数都是有限的，故算法的执行迟早会终止，即满足有穷性。当抵达 递归基时，算法将执行非递归的计算（这里是返回0）。

## 3.2 二分递归求数组的前n项和

往往对应于所谓`分而治之`的算法策略
```c
int sum(int A[], int lo, int hi)
{
    if (lo == hi)
        return A[lo];
    else
    {
        int mi = (lo + hi) >> 1;
        return sum(A, lo, mi) + sum(A, mi + 1, hi);
    }
}
```

## 3.3 如何正确线性递归斐波那契数列

> 为使分治策略真正有效，不仅必须保证以上两方面的计算都能高效地实现，还必须保证子问

> 题之间相互独立各子问题可独立求解，而无需借助其它子问题的原始数据或中间结果。否则，

> 或者子问题之间必须传递数据，或者子问题之间需要相互调用，无论如何都会导致时间和空间复 杂度的无谓增加。

之间那个设计得不好的递归就是没有考虑好上面所说的问题。

>    优化策略 为消除递归算法中重复的递归实例，一种自然而然的思路和技巧，可以概括为： 借助 一定量 的辅助空间，

> 在各子问题求解之后，及时记录下其对应的 解答 比如，可以从原问题出发自顶而下，每当遇到一个子问题，都首先查验它是否已经计算过，

> 以期通过直接调阅记录获得解答，从而避免重新计算。也可以从递归基出发，自底而上递推地得

> 出各子问题的解，直至最终原问题的解。前者即所谓的制表（tabulation）或记忆（memoization）

> 策略，后者即所谓的动态规划（dynamic programming）策略。



线性递归版fib()算法，消耗线性时间，但是耗费了O(n)的空间量。
```c
__int64 fib(int n, __int64& prev)
{ 
    if (0 == n) 
    {
        prev = 1;
        return 0;
    } 
    else
    { 
        __int64 prevPrev;
        prev = fib(n - 1, prevPrev); 
        return prevPrev + prev; 
    }
}
```

# 4 什么是迭代？

迭代是什么？从名词上就可以分析出来，迭代迭代，计算了这一轮的结果，然后把结果带入了下一轮的计算中！这一轮的输出是下一轮的输入，我们只需要给出迭代轮数（满足某个条件），迭代就可以继续。

迭代方式解决斐波那契数列
```c
__int64 fibI(int n)
{
    __int64 f = 0, g = 1;
    while (0 < n--)
    {
        g += f;
        f = g - f;
    }
    return f;
}
```

# 5 总结

现在就该知道迭代和递归是什么了。

无论设计递归算法还是设计迭代算法：递归到最终肯定有一个基解，从而能够终止递归；迭代肯定也需要有终止条件，不然就会无止境运算。

[数据结构与算法] 由递归转向迭代 递归与迭代的区别

上一节谈了算法的复杂度度量，为了公平度量，给出了抽象模型来度量。





他们就是图灵机和RAM模型，以计算次数来度量复杂度。

模型只是相当于给你度量的尺子，这一节来看尺子怎么用。

大O记号相当于是尺子的刻度。

大O记号并不是精确刻度，是在时间复杂度和空间复杂度取得平衡的一种科学记号，着重看DAS的潜力，而不是细节，快速看DAS的性能。

![在这里插入图片描述](/static/img/images/02555.png)

![在这里插入图片描述](/static/img/images/02556.png)

大O记号描述了趋势，往最坏的情况看算法性能。

小于符号。

![在这里插入图片描述](/static/img/images/02557.png)

大欧米伽符号。描述下届，算法最好的情况。

大于符号。

![在这里插入图片描述](/static/img/images/02558.png)

虽然有很多不同的记号，但我们还是最常用大O，因为它悲观看算法性能，描述了算法最差的度量，算法最差也差不多是大O了。

下面具体学怎么算大O，

也就是“刻度”

![在这里插入图片描述](/static/img/images/02559.png)

![在这里插入图片描述](/static/img/images/02560.png)

![在这里插入图片描述](/static/img/images/02561.png)

![在这里插入图片描述](/static/img/images/02562.png)

![在这里插入图片描述](/static/img/images/02563.png)

举例

![在这里插入图片描述](/static/img/images/02564.png)

这个算法就是指数级别的，而且不好优化。

![在这里插入图片描述](/static/img/images/02565.png)

![在这里插入图片描述](/static/img/images/02566.png)

![在这里插入图片描述](/static/img/images/02567.png)

[数据结构与算法]概论 P7-P9

[https://www.bilibili.com/video/av49361421?p=7](https://www.bilibili.com/video/av49361421?p=7)





![在这里插入图片描述](/static/img/images/02568.png)

![在这里插入图片描述](/static/img/images/02569.png)

![在这里插入图片描述](/static/img/images/02570.png)

![在这里插入图片描述](/static/img/images/02571.png)

**谈谈有穷性**

![在这里插入图片描述](/static/img/images/02572.png)

```
def hailstone(n):
    length = 1
    Hailstone = []
    Hailstone.append(n)
    while (1 < n):
        if (n % 2 == 1):
            n = (int)(3 * n + 1)
            Hailstone.append(n)
        else:
            n = (int)(n / 2)
            length += 1
            Hailstone.append(n)
    return length, Hailstone
print(hailstone(7))
print(hailstone(27))
```

output

![在这里插入图片描述](/static/img/images/02573.png)

![在这里插入图片描述](/static/img/images/02574.png)

其他学科探讨这个算法有穷性问题。（具体数学，专门探究各种算法背后的数学原理的）

我们这门课要研究的是，在正确性、确定性、可行性、有穷性已知的情况下，如何优化算法和数据结构，达到一个更好的计算过程。


**什么才是好算法？**

![在这里插入图片描述](/static/img/images/02575.png)

已知有：

![在这里插入图片描述](/static/img/images/02576.png)

如何度量数据结构和算法的好坏？

![在这里插入图片描述](/static/img/images/02577.png)

![在这里插入图片描述](/static/img/images/02578.png)

DSA

![在这里插入图片描述](/static/img/images/02579.png)

主要考虑时间成本，因为内存条不值钱，算法瓶颈往往卡在时间。

![在这里插入图片描述](/static/img/images/02580.png)

如何定义计算成本？

![在这里插入图片描述](/static/img/images/02581.png)

定义计算成本的时候，需要客观，理想化出一个模型出来，评价算法。

![在这里插入图片描述](/static/img/images/02582.png)

图灵机（抽象模型，为了度量算法复杂度）

![在这里插入图片描述](/static/img/images/02583.png)

如何用图灵机实现非负整数加一

最后复位，是为了规范化。

![在这里插入图片描述](/static/img/images/02584.png)

抽象模型，（抽象模型，为了度量算法复杂度）

![在这里插入图片描述](/static/img/images/02585.png)

![在这里插入图片描述](/static/img/images/02586.png)

[数据结构与算法]概论 P1-P6

我是一个专注技术分享的博主,尤其爱搞深度学习和单片机电子。你现在看到的是我的个人博客网站。