算法备忘录·时空复杂度分析

本文最后更新于:2022年2月23日 上午

一直以来,没能系统学习算法,是我心中的痛;现在学了 y 总的算法基础课,做做笔记,希望能够有所收获。
这是第八节,时空复杂度分析。

时空复杂度分析

  • 一般 ACM 或者笔试题的时间限制是 1 秒或 2 秒。在这种情况下,C++ 代码中的操作次数控制在 10710810^7\sim 10^8 为最佳。

在不同数据范围下,代码的时间复杂度和算法的选择:

  • n30n\leq 30,指数级别

    • dfs + 剪枝
    • 状态压缩 DP
  • n100n\leq 100O(n3)O(n^3)

    • floyd
    • DP
  • n1000n\leq 1000O(n2)O(n^2)O(n2logn)O(n^2\log n)

    • DP
    • 二分
    • 朴素版 Dijkstra
    • 朴素版 Prim
    • Bellman-Ford
  • n10000n\leq 10000O(nn)O(n\sqrt{n})

    • 块状链表
    • 分块
    • 莫队
  • n100000n\leq 100000O(nlogn)O(n\log n)

    • 各种sort
    • 线段树
    • 树状数组
    • set/map
    • heap
    • 拓扑排序
    • dijkstra+heap
    • prim+heap
    • Kruskal
    • spfa
    • 求凸包
    • 求半平面交
    • 二分
    • CDQ分治
    • 整体二分
    • 后缀数组
    • 树链剖分
    • 动态树
  • n1000000n\leq 1000000O(n)O(n)、常数比较小的 O(nlogn)O(nlog n)

    • 单调队列
    • hash
    • 双指针扫描
    • 并查集
    • kmp
    • AC自动机
    • 【常数比较小的 O(nlogn)O(nlogn) 的做法】sort、树状数组、heap、dijkstra、spfa
  • n10000000n\leq 10000000O(n)O(n)

    • 双指针扫描
    • kmp
    • AC 自动机
    • 线性筛素数
  • n109n\leq 10^9O(n)O(\sqrt{n})

    • 判断素数
  • n1018n\leq 10^18O(logn)O(\log n)

    • 最大公约数
    • 快速幂
    • 数位 DP
  • n101000n\leq 10^{1000}O((logn)2)O((\log n)^2)

    • 高精度加减乘除
  • n10100000n\leq 10^{100000}O(logk×loglogk)O(\log k \times \log\log k)kk 表示位数

    • 高精度加减
    • FFT/NTT

求时间复杂度

  • 循环
  • 递归:主定理(并不实用)
  • 动态规划:状态数量 * 状态转移的计算量
  • 小技巧
    • log210n3n\log_2 10^n\approx 3n
    • 自然数的倒数和的增长速度是 O(logn)O(\log n)
    • 质数的倒数和的增长速度是 O(loglogn)O(\log \log n)

求空间复杂度

  • 64MB 至多开 1600 万个 int

算法备忘录系列目录:
第一节 算法备忘录·基础算法
第二节 算法备忘录·数据结构
第三节 算法备忘录·STL
第四节 算法备忘录·搜索与图论
第五节 算法备忘录·数学知识
第六节 算法备忘录·动态规划
第七节 算法备忘录·贪心
第八节 算法备忘录·时空复杂度分析


算法备忘录·时空复杂度分析
https://justloseit.top/算法备忘录·时空复杂度分析/
作者
Joker
发布于
2022年2月21日
更新于
2022年2月23日
许可协议