复杂度分析

时间复杂度

时间频度：代表一个算法中的语句执行次数，其又称为语句频度。记作,n为问题的规模
为了探究n和T(n)变化的关系，引入时间复杂度的概念。
不同于时间频度，时间复杂度考察的是当输入规模趋于无穷时，时间频度的渐近情况。
时间复杂度的具体定义为：若有某个辅助函数f(n)，使得的极限值（当n趋近于无穷大时）为不等于0的常数，则称f(n)是T(n)的同数量级函数。记做
称为算法的渐进时间复杂度，简称时间复杂度
在数学上，O符号（Landau符号）用来描述一个函数数量级的渐近上界。因为O符号表示法并不是真实代表算法的执行时间，而是表示代码执行时间的增长变化趋势。
代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度 （asymptotic time complexity），简称时间复杂度。
不同时间规模下的算法选择：
  • n ≤ 30, 指数级别，dfs+剪枝，状态压缩
  • n ≤ 100, O(n^3), DP, floyd
    时间复杂度的计算
    1. 单纯的循环
        • 一般 一层循环 O(n)，两层循环嵌套O(n^2)
        • 特殊的比如单调栈，单调队列，滑动窗口，筛素数等，虽然两层循环，但内层循环 j 只增不减，因而也是O(n)复杂度
    1. 递归
        • 主定理
        • 快排 or 归并排序 每一层循环都是O(n), 共有O(logn)层。所以总共为 O(nlogn)
    1. 并查集
        2. 单纯路径压缩，时间复杂度最坏为O(nlogn)
        再加上按秩合并，时间复杂度为O(loglogn)
    1. 搜索
        • 画一颗树来看
        • 全排列 (n+1)!. 最后一层的节点个数为 n!, 每个节点下面执行n次，所以为 (n+1)!