算法与数据结构（初识）

算法

有限时间内解决特性问题的指令或操作步骤
查字典 ：二分法
整理扑克：插入排序（处理小型数据集高效）
货币找零：贪心算法

数据结构

组织和存储数据的方式。数据增删改查。
程序=算法+数据结构

算法效率评估

实际测试：硬件配置等干扰，浪费资源
理论估算：渐进复杂度分析。随着输入数据大小的增加，时间和空间的增长趋势，不是具体值。

迭代与递归

• 迭代(自下而上，从最基础步骤累加)

for、while
f(n)=1+2+…+n

• 递归(自上而下，将问题切分为同类型小问题)

递、终止条件、归
f(n)=n+f(n-1)
调用栈：每调自身，分配内存，存储局部变量、调用地址和其他信息。上下文存储在“栈帧空间”，函数返回才释放。一般比迭代更耗费空间。
递归调用函数会产生额外开销，递归比循环时间效率低。

尾递归：函数在返回前的最后一步才进行递归调用。则该函数可以被编译器或解释器优化，使其在空间效率上与迭代相当。这种情况被称为尾递归（tail recursion）。
普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下文。
尾递归：递归调用是函数返回前的最后一个操作，这意味着函数返回到上一层级后，无须继续执行其他操作，因此系统无须保存上一层函数的上下文。（递的过程实现业务逻辑，归的过程只需返回）
许多编译器或解释器并不支持尾递归优化。如：python。仍然可能出现栈溢出。

递归树：处理分治算法、递归比迭代更直观。
斐波那契数列：f(n) = f(n-1) + f(n-2)。n层递归树
体现了将问题拆分为更小子问题的思维，即分治法
算法角度：搜索、排序、回溯、分治、动态规划运用该思维
数据结构角度：适合处理链表、树、图等

• 递归与迭代

递归求和：求和操作在归阶段，意味着最初被调用的函数实际上是最后完成其求和操作的，这种工作机制与栈的“先入后出”原则异曲同工。

递：当函数被调用时，系统会在“调用栈”上为该函数分配新的栈帧，用于存储函数的局部变量、参数、返回地址等数据。
归：当函数完成执行并返回时，对应的栈帧会被从“调用栈”上移除，恢复之前函数的执行环境。

def for_loop_recur(n: int) -> int:
    """使用迭代模拟递归"""
    # 使用一个显式的栈来模拟系统调用栈
    stack = []
    res = 0
    # 递：递归调用
    for i in range(n, 0, -1):
        # 通过“入栈操作”模拟“递”
        stack.append(i)
    # 归：返回结果
    while stack:
        # 通过“出栈操作”模拟“归”
        res += stack.pop()
    # res = 1+2+3+...+n
    return res
"""
迭代与递归可以相互转换，但不值得这样做：
- 转化后代码难理解
- 模拟调用栈困难
"""

时间复杂度

时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大时的增长趋势。用O(n)表示，函数渐进上界。T(n)表示算法函数。O(n)由最高阶的项来决定。

常数阶
线性阶：
函数渐进上界：O(f(n))即O(n)
如何确定：f(n)----> 1、统计操作数量(忽略常数项，省略所有系数，循环嵌套用乘法) 2、判断渐进上界(取最大阶)

常见类型：$O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(2^n)<O(n!)$
常数阶<对数阶<线性阶<线性对数阶<平方阶<指数阶<阶乘阶
指数阶：每轮增长一倍。常出现在递归中。穷举、暴力搜索、回溯中常见。数据规模大不可接受，使用动态规划或贪心算法解决。
对数阶：每轮缩减一半。也常出现在递归函数中。常出现：基于分治策略算法，一分为多化繁为简。$O(lo{g}_{k}n)$
线性对数阶：常出现在嵌套循环中。线性+一分为二。主流排序算法：快排、归并排序、堆排序。
阶乘阶：数学上的全排列。通常递归实现。

最差时间复杂度：函数渐进上界 O表示 （更实用，更安全）
最佳时间复杂度：函数渐进下界 Ω表示
平均时间复杂度：复杂算法计算平均时间复杂度困难

空间复杂度

衡量算法占用内存空间随着数据量变大时的增长趋势。通常只关注最差空间复杂度。使用内存空间：

• 输入空间(一般不统计)：存储输入数据
• 暂存空间(一般统计)：算法运行过程中变量、对象、函数上下文数据
  • 暂存数据：保存运行中的变量、常量、对象等。
  • 栈帧空间：用于保存调用函数的上下文数据。每次调用函数会在栈顶部创建一个栈帧，函数返回后，栈帧空间会释放。
  • 指令空间：保存编译后的程序指令。统计中忽略不计。
• 输出空间(一般统计)：输出数据

循环调用function()，每轮中都返回并释放了栈帧空间，因此空间复杂度O(1)。
递归调用function()，会同时存在n个未返回的函数，占用O(n)的栈帧空间。
常数阶：常量、变量、对象、循环等。
线性阶：常见与n成正比的数组、链表、栈、队列等。
平方阶：常见与矩阵和图。
指数阶：常见于二叉树，满二叉树。
对数阶：常见于分治法。归并排序。

数据结构

逻辑结构

线性：数组、链表、栈、队列、哈希表（一对一）
非线性：

• 派生关系：树、堆、哈希表（一对多）
• 网状关系：图（多对多）

物理结构（数据在内存中的存储方式）

连续：数组(静态数据结构，可通过重新分配内存实现长度变化，一定动态性)
分散：链表(动态数据结构)
所有数据结构都是基于数组、链表或二者的组合实现。
基于数组可实现：栈、队列、哈希表、树、树、堆、图、矩阵、张量等
基于链表可实现：栈、队列、哈希表、树、堆、图等

基本数据类型

整数、浮点、字符、布尔
比特、字节

数字编码

原码：有符号位—> $-2^7到2^7-1$—>原码加法计算有问题
反码：原码—>反码---->计算—>原码 没有问题 但是正0和负0歧义
补码：引入补码解决 负零的反码加1变为9位，溢出的1舍去解决上面的问题 （1000 0000代表-128）
计算机内部硬件电路主要基于加法运算设计。
浮点数编码：1位符号、8为指数、23位分数 （存在指数位，因此取值范围大于整数，代价是牺牲精度）

字符编码

字符和二进制数之间的对应关系
ASCII码：7位二进制表示128个字符
GBK字符集：其中ASCII使用一个字节、汉字使用连个字节
Unicode字符集：统一码
将所有字符储存为等长的编码，解决计算机如何分辨字符码点
UTF-8编码：长度为1字节的字符，高位设置为0。可以兼容ASCII且节省空间。
UTF-16编码：使用2或4字节表示字符
UTF-32编码：使用4字节表示字符。
大多数编程语言采用UTF-16或UTF-32这类等长编码。优点：随机访问O(n)时间，字符计数O(1)时间，字符串操作更容易。
python中str使用Unicode编码，字符串长度取决于其中的最大Unicode码点，全是ASCII字符则占用1字节，超过了但是在基本多语言平面内则用2字节，否则用4字节。