时间复杂度分析
时间复杂度分析ψ(｀∇´)ψ
基本操作数ψ(｀∇´)ψ
计算机执行的一次赋值，一次运算，一次对内存的访问都叫做一次基本操作。
一般都会用一个算法在某个数据规模下的基本操作数进行计数以描述算法的复杂度。
时间复杂度ψ(｀∇´)ψ
一般来说，衡量一个算法的时间复杂度，都需要在数据规模下看他的运行时间增长趋势。
说白了，就是用一个函数 \(f\)，对于一个算法建立起从数据规模到运行时间的映射。
而运行时间一般都使用基本操作的数量来描述，再根据计算机实际的硬件配置（单位时间能进行多少次基本操作）来看在计算机上实际的运行时间。
时间复杂度主要分四种：
- 最坏复杂度，描述算法最坏情况下的运行效率，直接说时间复杂度一般都指最坏复杂度。
- 最优复杂度，描述算法最好情况下的运行效率，不常用。
- 平均复杂度（期望复杂度），当输入数据规模随机的时候的复杂度，就是各个数据规模下复杂度的平均。
- 均摊复杂度，多次操作的总复杂度除以操作次数，就是单次操作的复杂度，（注意和平均复杂度做区分）
渐进记号ψ(｀∇´)ψ
渐进符号是函数的阶的规范描述。简单来说，渐进符号忽略了一个函数中增长较慢的部分以及各项的系数（在时间复杂度相关分析中，系数一般被称作“常数”），而保留了可以用来表明该函数增长趋势的重要部分。
所以说在计算时间复杂度的时候（在渐进意义上）一般都是直接忽略掉描述基本操作数的多项式的常数项还有一些低次项对于算法时间复杂度的影响的。
如果你想要卡常，不忽略也是可以的，不过这就不是严谨的时间复杂度的记法了。
- \(\Theta\)：对于两个函数 \(f(n), g(n)\)，如果存在 \(c_1,c_2,n_0 > 0\)，使得 \(\forall n\ge n_0, 0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)\)，则记为 \(f(n) = \Theta(g(n))\)，用于描述算法的上下界。
- \(O\)：对于两个函数 \(f(n), g(n)\)，如果存在 \(c, n_0 > 0\)，使得 \(\forall n\ge n_0,0 \le f(n) \le c \cdot g(n)\)，则记为 \(f(n) = O(g(n))\)，用于描述算法的上界，大部分时候都用这个描述，不过算法使用的时候的最坏复杂度不是大 \(O\) 记号，用 \(\Theta\) 表示最坏复杂度是完全可以的，只不过大部分时候都只比较方便证明出上界，所以用大 \(O\) 用的多，就是说，在一定情况下 \(O\) 可以表示最坏复杂度。
- \(o\)：就是 \(O\) 去掉等号变成 \(<\)。
- \(\Omega\)：\(\ge\)。
- \(\omega\)：\(>\)。
一些性质：
- \(f1(n) + f2(n) = O(\max(f1(n), f2(n)))\) （两个函数之和的上界是他们当中在渐进意义上较大的函数）。
- \(f1(n)\cdot f2(n) = O(f1(n) \times f2(n))\)。
- \(\forall a \not=1, \log_a(n) = O(\log_2(n))\)，所以渐进时间复杂度的 \(\log\) 都表示 \(\log_2\)，因为对于所有对数函数，不管底数如何，增长率 (\(\Theta\)) 都是相同的，为了讨论方便，都换成底数为 \(2\) 的对数。
Extend
由换底公式 \(\log_ab = \dfrac{\log_cb}{\log_ca}\) 可以知道：\(\log_a n=\log_2 n\times\log_a2\)。
而 \(\log_a2\) 是一个常数，在渐进意义下就被忽略了。
常数因子ψ(｀∇´)ψ
一般说一个算法有几倍常数的时候，一般是说实际跑起来的基本操作数的数量级是算出来的时间复杂度的几倍。
比如我有一个算法是 \(O(n)\) 的，但是实际上跑出来的基本操作数是 \(4n\) 级别的，那我就会说我的算法有 4 倍常数。
不过感觉这个是一个比较民间的叫法。
分析时间复杂度ψ(｀∇´)ψ
就是看一看进行了多少次基础操作就行了。
递归算法画递归树算每层每个节点复杂度比较好，也可以视情况用主定理，但是主定理就是递归树证明的（。
然后递推，DP 啊之类的就看循环层数和循环区间乘一下就可以了。
大部分都是，算每一轮操作的复杂度，然后乘上轮数。
或者是算每一层的复杂度。
主定理ψ(｀∇´)ψ
对于一个递归式算法 \(T(n) = aT(\dfrac{n}{b}) + f(n)\)，
其中 \(n\) 是问题规模大小，\(a\) 是子问题的个数，\(\dfrac{n}{b}\) 是每个子问题的大小（规模），\(f(n)\) 是将原问题分成子问题和将子问题的解合并的时间。
可以得到一个式子：
举几个例子：
应用1
对于二分，
那么 \(T(n) = T(n/2) + \Theta(1)\)，
解释：二分每次把子问题规模缩小一半，每次只递归一遍，所以（处理的）子问题个数是 \(a = 1\)。
对于 condition 1，显然 \(\displaystyle n^{\log_b(a-\epsilon)}\) 在 \(\epsilon > 0\) 时无意义，肯定不是
对于 condition 2，因为 \(\displaystyle n^{\log_b(a)} = 1\)，且 \(f(n) = \Theta(1)\)，我们可以令 \(k = 0\)，然后发现 \(\displaystyle n^{\log_b(a)}\log^k n\) 这坨就等于 \(\Theta(1)\)，所以复杂度是 \(\Theta(\log^{0 + 1} n) = \Theta(\log n)\)。
然后如果带一个 \(Check\) 的话，你可能会写出 \(T(n) = T(n/2) + \Theta(n)\)，但这个不完全对的。
因为你每次 \(n\) 会缩小，Check 的规模就变了，计算方式应该是直接计数。
二分最多调用 \(O(\log n)\) 次 check，check 的总复杂度是 \(n + n/2 + n/4 + .... = 2n\)。
然后 \(\sum (\log n \times \text{check}) = \log n \times \sum \text{check} = n \log n\)。
应用2
对于归并排序，
\(T(n) = 2T(n / 2) + \Theta(n)\)。
解释：每次把子问题二分，规模缩小一半，每次递归两边，所以（处理的）子问题个数是 \(a = 2\)。
然后还是一个 condition 一个 condition 的看。
发现 \(\displaystyle n^{\log_b(a)} = \Theta(n)\)，你发现和二分的有点像，都是 \(\displaystyle n^{\log_b(a)} = f(n)\)，然后令 \(k = 0\).
所以复杂度 \(\Theta(n\log n)\)。
应用3
\(T(n) = 9T(n/3) + n\).
发现 \(\displaystyle n^{\log_b(a)} = 2\)，\(n^2 > n\)，所以复杂度 \(\Theta(n^2)\)。
Warning
对于 \(a\) 的确定，二分和归并排序用“递归了那几边”是可行的。
对于线段树单点改也是可以的，但是对于线段区间查就不行了，因为线段树区间查有一个 \([l, r]\subset [ql, qr]\) 的剪枝。
需要单独分讨分析，不能主定理。