# 算法简介记录

# 1. 流程

  • 由简单到复杂
    • 验证一步走一步
    • 多打印中间结果
  • 先局部后整体
    • 没思路时先细分
  • 先粗糙后精细
    • 变量更名
    • 语句合并
    • 边界处理

# 2. BigO

一个算法的评价主要从时间复杂度和空间复杂度来考虑,而评定的单位就是用大O符号来说明

符号 名称
O(1) 常数(阶,下同)
O(log*n) 迭代 (opens new window)对数 (opens new window)
O(log n) 对数
O[(log n)^c] 多对数
O(n) 线性,次线性
O(n log n) 线性对数 (opens new window),或对数 (opens new window)线性、拟线性、超线性
O(n^2) 平方
O(n^c),Integer(c>1) 多项式,有时叫作“代数”(阶)
O(c^n) 指数,有时叫作“几何”(阶)
O(n!) 阶乘 (opens new window),有时叫做“组合”(阶)

# 3. 记录

算法

  • 排序算法:快速排序、归并排序、计数排序
  • 搜索算法:回溯、递归、剪枝
  • 图论:最短路径、最小生成树、网络流建模
  • 动态规划:背包问题、最长子序列、计数问题
  • 基础技巧:分治、倍增、二分、贪心

数据结构

  • 数组与链表:单 / 双向链表、跳舞链
  • 栈与队列
  • 树与图:最近公共祖先、并查集
  • 哈希表
  • 堆:大 / 小根堆、可并堆
  • 字符串:字典树、后缀树

参考

上次更新时间: 2023-01-16 03:44:08