算法刷题笔记

由数据范围反推算法复杂度和算法内容

• 当n特别小，n <= 30, 一般都直接暴搜就可以了，指数级别，常用dfs + 剪枝，状态压缩dp
• n <= 100 , O(n^3), floyd, dp
• n <= 1000, O(n^2), O(n^2 * logn),dp,二分
• n <= 10^5, O(n * logn)，各种排序，堆，二分
• n <= 10^6, O(n), 以及常数较小的O(nlogn)算法，hash,双指针扫描，kmp,
• n <= 10^7, 只能O(n)的算法来做，双指针，kmp
• n <= 10^9, O(根号n)
• n <= 10 ^ 18，O(logn)

分析代码复杂度

• 看循环
• 递归，算法复杂度的话，可以参考主定理 (opens new window)
  • 快排，每次排序需要O(n)的复杂度，但总共需要O(logn)次，所以总复杂度O(nlogn)
  • 二分，看总共比较几次，O(logn)
• 双指针算法，内循环指针只增不减，O(n)
• 单调栈，类似于双指针，O(n)
• kmp，O(m + n)
• 并查集，加上路径压缩，O(logn)
• 堆，O(nlogn)
• 全排列，O(n!*n)
• 深度优先遍历。宽度优先遍历，就是遍历一下所有的点+边，时间复杂度O(n + m)
• spfa,匈牙利算法，最大流 理论复杂度比较高，但是实际运行效果非常好
• log2(10^x) 约等于 3x
• 动态规划，一共的状态数 * 没事状态的计算量