Please enable JavaScript.

Coggle requires JavaScript to display documents.

漫画算法：小灰的算法之旅 - Coggle Diagram

- - - - O(nlogn):快速，归并，堆
      - 线性：技术，桶，基数
      - O(n^2):冒泡，选择，插入，希尔
    - - 稳定排序
      - 不稳定排序：排序打乱了相同值排序前顺序
  - - - 逻辑1：相邻元素的两两比较。比如第一个数和第二个数比较，如果第一个数更大，它们就交换位置。然后新的第二个数继续和第三个数比较，如果它更大，又交换位置。通过这种方式，最大的数会像气泡一样一路"冒"到最顶端。接下来重复相同的步骤，去找次大的数，让它"冒"到倒数第二的位置。然后是第三大的数……依次类推，直到整个数组排序完成。核心思想：每一轮都把当前未排序部分的最大值"冒泡"到正确位置。
      - 逻辑2：检测"有没有排好序"
        
        每一轮在最后会记录一下这一轮有没有进行交换位置，如果这一轮完全没有进行交换位置的话，那就说明序列已经排好了，就可以直接输出答案，可以停止工作
      - 逻辑3：记住最后一次交换的位置，下一轮只比较到那个位置就够了
  - - - 极值（最大或最小）在错误的一端时，鸡尾酒排序特别有效
  - - - 大问题分成小问题解决
        
        平均时间 O(n log n) 最坏情况 O(n²)，不稳定排序
        
        选一个基准，把比它小的放左边，比它大的放右边，然后对左右两边重复这个过程
    - - 一个指针扫描，一个指针记边界
        
        Draw a line to divide into two sides 从左往右扫描：遇到小的 → 扔到线左边（mark往右移）遇到大的 → 不管，继续走
    - - 递归是系统自动帮你记住'待处理的任务'，非递归就是你自己用栈来记住这些任务
      - 自己用便签纸记待办事项
- - - - 物理结构
        
        数组
        
        ：有限相同类型的变量组成的有序集合；顺序存储；随机访问
        
        列表：动态可扩展的数组
        
        元组tuple：不可变集合
        
        操作
        
        读取，更新元素 O(1)
        
        插入 O(n)
        
        删除O(n) or O(1)非主流
        
        适合
        
        读多写少: 经常查询,很少改动
        
        链表
        
        分类
        
        单向链表
        
        ：data+指正next
        
        双向链表
        
        操作
        
        查找节点 O(n)
        
        更新节点
        
        插入节点 O(1)只考虑本操作
        
        尾部插入
        
        头部插入
        
        中间插入
        
        删除元素O(1) 只考虑本操作
        
        ：物理上非连续非顺序的数据结构，有若干node组成；随机存储；顺序访问
      - 哈希表 ≈O(1)
        
        :key(字符串为主） value
        
        名字找数据，Key(名字)转成Index(柜子号)
        
        操作
        
        写put
        
        开发寻址法：占满就找下一个空位
        
        链表法
        
        ：钥匙串: 一个环上挂多把钥匙! 🔑
        
        get读
        
        算Index，去那个位置找，顺着链表比对Key,找到就返回Value
      - 逻辑结构
        
        栈
        
        操作O(1)
        
        入栈push
        
        针对栈顶
        
        pop出栈
        
        先入后出
        
        应用
        
        回溯历史
        
        面包屑导航：用户浏览页面回溯到上一级
        
        递归
        
        队列
        
        先入先出
        
        操作
        
        enquenue 入队
        
        出队dequeue
        
        应用
        
        重演历史
        
        爬虫
        
        双端队列deque
        
        可以从队头/队尾入队或出队
        
        优先队列
        
        优先级高的，先出队
        
        基于二叉堆，非线性数据结构
    - - 二叉堆
        
        应用
        
        排序算法的堆排序
        
        用二叉堆实现优先队列
        
        :本质完全二叉树；顺序存储
        
        分类
        
        最大堆
        
        最小堆
        
        要找最大的K个 → 用最小堆（size=K）
        要找最小的K个 → 用最大堆（size=K）
        
        操作
        
        插入节点
        
        删除节点
        
        构建二叉堆
      - 逻辑结构
        
        二叉树 O(logn)
        
        物理存储：链式，数组
        
        类型
        
        完全二叉树：最后一个节点前的节点齐全
        
        满二叉树：每一个分支都是满的
        
        二叉查找树：每个节点是一个数，左边的孩子都比它小，右边的孩子都比它大
        
        应用
        
        查找
        
        维持相对顺序
        
        遍历
        
        深度优先遍历
        
        前序遍历（先自己，再左右）根 → 左 → 右
        
        1 more item...
        
        中序遍历（左自己右）左 → 根 → 右
        
        1 more item...
        
        后序遍历（左右后自己）左 → 右 → 根
        
        1 more item...
        
        广度优先遍历:一层一层横着扫
    - - 多对多的关联关系
    - - 跳表，位图
      - 哈希链表
        
        应用：缓存淘汰算法LRU least recently used
- - - - 1
        
        T(n) = 3n
      - 固定次数的操作- O(1)
      - n 很大,最高次方碾压其他项
        
        eg.T(n) = n² + 100n + 5000 T(n) = O(n²)
        
        n足够大，O(1)<O(logn)<O(n)<O(n^2)
      - 系数不影响增长趋势
        
        T(n) = 0.5n² 和 T(n) = 100n² 都写成 O(n²)
        
        T(n) = 3n O(n)
    - - eg.双重循环:挨个盘问: O(n²)
        3号,你后面有人和你票号一样吗?
        1号,你后面有人和你票号一样吗?...
        VS字典/哈希表:O(n)
        3号进 → 本子记: "3号✓"
        1号进 → 本子记: "1号✓"
        2号又来 → 翻本子: "2号已经进过了!"
      - 情形
        
        常量空间 O(1) ;只用1个变量
        
        线性空间 O(n)需要n个格子(数组/列表)
        
        students = ["小明", "小红", "小刚"]
        
        二维空间 O（n^2)
        
        递归空间 O(n) 递归函数调用n层