Hello Algo学习笔记 1. 复杂度分析 + 栈

递归

递归 recursion 和常用的循环迭代不一样，这种策略算法通过调用自身来解决问题，它主要包含两个方面：

递：程序不断深入调用自身，通常传入更下或更简化的参数，直到达到“终止条件”
归：出发“终止条件”之后，程序从最深处开始逐层返回，并且汇聚每一层的结果。

从实现的角度来说，设计递归算法主要需要三个主要的条件

终止条件：什么条件下终止“递”，从而开始“归”
递归调用：对应“递”，函数里应该不断调用自身，通常传入更小的参数
返回递归的结果：对应“归”，将当前递归层级的结果返回到上一级中。

虽然从计算的角度来看，迭代与递归可以获得相类似的结果，但是它们是两种完全不同的思考和解决问题的范式。

迭代：“自下而上”地解决问题，从基础的步骤开始，然后不断重复或者累加这些步骤，直到完成任务。
递归：”自上而下“地解决问题，如果问题和其子问题具有相同的形式，将原问题拆分为更小的部分，通过确定终止条件和返回结果来完成递归的调用。

调用栈

递归函数每次调用自身的时候，系统都会为其开启新的函数分配内存，来存储局部变量、调用地址和其他信息，这就会导致递归比迭代更消耗内存空间。

函数的上下文数据都存储在称为”栈帧空间“的内存区域中，直到函数返回之后才会被释放。
递归函数会产生额外的开销。因此递归通常比循环的时间效率更低。

尾递归

如果函数在返回前的最后一步才进行递归调用，则这种递归就被称为尾递归 tail recursion，这种尾递归可以通过编译器来实现自动优化，递归和迭代的特点对比如下：

	迭代	递归
实现方式	循环结构	函数调用自身
时间效率	效率通常较高，无函数调用开销	每次函数调用都会产生开销
内存使用	通常使用固定大小的内存空间	累积函数调用可能使用大量的栈帧空间
适用问题	适用于简单循环任务，代码直观、可读性好	适用于子问题分解，如树、图、分治、回溯等，代码结构简洁、清晰

时间复杂度

我们常说的时间复杂度，其实是指算法的渐进上界，其数学定义如下：

若存在正实数$c$和实数$n_0$，使得对于所有的$n> n_0$，均有$T(n)\le c \cdot f(n)$，则可以认为$f(n)$给出了$T(n)$的一个渐进上界，记为$T(n)=O(f(n))$。

计算渐进上界其实就是寻找一个函数$f(n)$，使得当$n$趋于$\infty$的时候，$T(n)$和$f(n)$处于相同的增长级别。

计算时间复杂度，可以遵循下列的计算技巧：

忽略$T(n)$中的常数项，因为常数项对时间复杂度都不产生影响
省略所有系数
循环嵌套的时候使用乘法
时间复杂度由$T(n)$中的最高阶项来决定

常见的时间复杂度类型有：
$$
O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n) < O(n!)
$$
指数阶对应的是每次增加一倍的情况，类似与”细胞分裂“的过程，而对数阶对应的是每次缩减一倍的情况。

空间复杂度

空间复杂度的推算方法与时间复杂度大致相同，只是将统计的对象从“操作数”变为了“使用内存大小”，与时间复杂度不同，我们只需要关注于最差空间复杂度，因为内存空间是一项硬性要求，我们必须确保所有的输入数据都有足够的内存空间预留。最差空间复杂度表示以算法运行中的峰值内存为准。

原码、反码和补码

原码、反码和补码的引入都为了加速计算机的运算，所有的数字都是以“补码”的形式存储在计算机中的，三者的定义如下：

原码 sign-magnitude：将数字的最高位视为符号位，用0表示正数，1表示负数，其余的位置用于存放数字
反码 1’s complement：除了最高位符号位不变，其余位置均取反
补码 2’s complement：将反码+1

出现反码的原因是计算为了方便计算减法，直接使用反码相加就能够同时计算加法和减法；为了解决0在存储的过程中出现+0和-0的区别，使用补码来让0的补码也是0，消除了零正负奇异的问题。

数组

数组array是一种线性的数据结构，其将相同类型的数据存储在连续的内存空间当中，我们将元素在数组中的位置称为该元素的索引index，索引本质上是内存地址的偏移量，所以数组中的第一个元素的索引是0。由于索引的设计，我们访问数组中的任意一个元素的时间复杂度为$O(1)$。数组支持随机访问。

链表

链表linked list是一种线性数据结构，其中每一个元素都是一个节点，各个节点通过“引用”（指针）相连接，引用记录了下一个节点的物理地址。链表的设计使得其可以分散在内存的各处，并且它们的内存地址无须连续。

用python实现链表的Node：

class ListNode:
    def __init__(self, val: int):
        self.val: int = val					#当前节点值
        self.next: ListNode | None = None 	#指向下一个节点的指针

链表不支持随机访问，访问元素的时间复杂度为$O(n)$。

表 4-1 数组与链表的效率对比

	数组	链表
存储方式	连续内存空间	分散内存空间
容量扩展	长度不可变	可灵活扩展
内存效率	元素占用内存少、但可能浪费空间	元素占用内存多
访问元素	$O(1)$	$O(n)$
添加元素	$O(n)$	$O(1)$
删除元素	$O(n)$	$O(n)$

栈

栈stack是一种先进后出的数据结构，栈一般包括如下的一些操作：

表 5-1 栈的操作效率

方法	描述	时间复杂度
`push()`	元素入栈（添加至栈顶）	$O(1)$
`pop()`	栈顶元素出栈	$O(1)$
`peek()`	访问栈顶元素	$O(1)$

栈的实现有几种方式，第一种是基于链表的实现

class LinkedListStack:
    """基于链表的栈实现"""
    
    def __init__(self):
        self._peek: LinkNode | None = None
        self._size: int = 0
            
    def size(self) -> int:
        return self._size
    
    def is_empty(self) -> bool:
        return not self._peek
    
    def peek(self) -> int:
        if self.is_empty():
            raise IndexError("栈为空")
        return self._peek.val
    
    def push(self, val: int):
        node = LinkNode(val)
        node.next = self._peek
        self._peek = node
        self._size += 1
     
    def pop(self) -> int:
        val = self.peek()
        self._peek = self._peek.next
        self._size -= 1
        return val
    
    def to_list(self) -> list[int]:
        """转换成list方便调试"""
        arr = []
        node = self._peek
        while node:
            arr.append(node.val)
            node = node.next
        return arr.reverse()

第二种是基于列表的实现

class ArrayStack:
    def __init__(self):
        self._stack: list[int] = []
    
    def size(self) -> int:
        return len(self._stack)
    
    def is_empty(self) -> bool:
        return self._stack == []
    
    def push(self, item: int):
        self._stack.append(item)
    
    def pop(self) -> int:
        if self.is_empty():
            raise IndexError("栈为空")
        return self._stack.pop()
    
   	def peek(self) -> int:
        if self.is_empy():
            raise IndexError("栈为空")
        return self._stack[-1]
    
    def to_list(self) -> list[int]:
        return self._stack