算法基础

1. 时间复杂度

   适用于大多数场景

   一个 for 循环 O(n)

   两个 for 循环 O(n²)

   三个 for 循环 O(n³)

   每次减少一半 O(log n)

2. 空间复杂度

   适用于大多数场景

   创建常数项变量 O(1)

   创建一个list O(n)

3. 递归

   1、定义

   • 在函数内部，可以调用其他函数。
   • 如果一个函数在内部调用自身本身，这个函数就是递归函数。

   2、递归特性

   • 必须有一个明确的结束条件
   • 每次进入更深一层递归时，问题规模相比上次递归都应有所减少
   • 递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的
   • 每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。
   • 由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）

4. 查找

   线性查找（linear_search）

   二分查找（折半查找）（binary_search）

5. 排序
   1. low b 三人组
      1. 冒泡排序（bubble_sort）
      2. 插入排序（insert_sort）
      3. 选择排序（select_sort）
   2. 🐂b 三人组
      1. 堆排序（heap_sort）
      2. 归并排序（merge_sort）
      3. 快速排序（quick_sort）
   3. 希尔排序
   4. 桶排序
6. 数据结构
   1. 列表
   2. 栈
   3. 队列
   4. 链表
      1. 单链表
      2. 双链表
   5. 哈希表
   6. 树
      1. 二叉树
      2. AVL树
   7. 动态规划
   8. 设计模式