算法初入门(一)——认识算法

Admsec2024-05-022024-05-26

算法初入门(一)——认识算法

前言

我是配套着 Hello 算法这个开源的在线教程学的，以前以为算法、设计模式这些不重要，没有学这些就去做项目，做的是真头疼~~（造了一堆shi山代码，效率还低~~

什么是算法

算法不是很高深的东西，它就藏在我们的生活中。

有个民间流传的公式：程序 = 算法 + 数据结构

比如查字典——确定要寻找的字的拼音字母，假定是”g”，翻开一字典的一半，如果字典上写的拼音字母大于”g”，我们就在小于”g”的那一半页数再翻开一半…循环此方法直至找到对应的那个拼音字母；把字典换成数组，拼音字母换成要查找的元素，就是”二分查找”

生活中有很多事情都有算法，例如：整理扑克——插入排序(对小型数据集非常有效)、货币找零——贪心算法等等

算法和数据结构

算法的定义：算法（algorithm）是在有限时间内解决特定问题的一组指令或操作步骤
数据结构的定义：数据结构（data structure）是计算机中组织和存储数据的方式。
算法与数据结构的关系：可以把数据结构想象成一个容器，算法就是水，它们的关系就是——有容器才能装水，不同的水有不同的作用，相对的，算法也有很多种，且算法之间的执行效率相差可能很大。

迭代和递归

迭代是一种重复执行某个任务的控制结构。for 循环和 while 循环都属于迭代。

递归是一种算法策略，通过函数调用自身来解决问题。它通常是把一个问题分成几个更小的子问题，直到预料的基本情况时停止，这个”基本情况”一定要是已知的。

一般来说递归的时间效率和空间效率都比迭代的低和大，因为每次递归都要分配内存给新的函数。

递归又分为普通递归和尾递归，它们之间的区别就是普通递归的计算操作是在”归”里面的，所以在”递”的时候要保存上下文，直到”归”将保存的上下文当成下一层的输入进行逐层传递；而尾递归的计算操作在”递”的过程中执行的，”归”只是返回结果，并没有计算操作，所以不用保存上下文，在被编译器或者解释器优化后和迭代的空间效率相当。

一般递归都有三个要素：1.终止条件；2.递归调用；3.遵循先进后出的原则逐层返回结果。

普通递归（1+2+…+n 的求和操作）：

def recur(n: int) -> int:
    """递归"""
    # 终止条件
    if n == 1:
        return 1
    # 递：递归调用
    res = recur(n - 1)
    # 归：返回结果
    return n + res

普通递归执行过程

尾递归（1+2+…+n 的求和操作）：

def tail_recur(n, res):
    """尾递归"""
    # 终止条件
    if n == 0:
        return res
    # 尾递归调用
    return tail_recur(n - 1, res + n)

尾递归执行过程

时间复杂度

概念：时间复杂度统计的是算法运行时间随着数据量变大时的增长趋势。

# 算法 A 的时间复杂度：常数阶
def algorithm_A(n: int):
    print(0)
# 算法 B 的时间复杂度：线性阶
def algorithm_B(n: int):
    for _ in range(n):
        print(0)

算法A的运行时间不受n的增大而增大，是常数阶
算法B中的运行时间受for循环中的参数n的增大而增大，是线性阶
总之，运行时间与n无关联的都是常数阶，时间复杂度为O(1)；有关联的则为其他阶，比如线性阶、平方阶等等

如何推算时间复杂度？

统计操作数量，操作数量中的各种系数、常数项都可以忽略
循环嵌套时使用乘法。总操作数量等于外层循环和内层循环操作数量之积，每一层循环依然可以分别套用第 1. 点和第 2. 点的技巧。
判断渐近上界，也就是由最高阶的项来决定时间复杂度，因为当 n 趋于无穷大的时候，最高阶起主导作用。

给定一个函数，统计操作数量：

def algorithm(n: int):
    a = 1      # +0（技巧 1）
    a = a + n  # +0（技巧 1）
    # +n（技巧 2）
    for i in range(5 * n + 1):
        print(0)
    # +n*n（技巧 3）
    for i in range(2 * n):
        for j in range(n + 1):
            print(0)