主定理
递推式子的时间复杂度求法
\[T(n) = aT(\frac{n}{b}) + f(n), n >= b \]其中：
- $n $是问题规模的大小
- \(a\) 是原问题的子问题个数
- \(\frac{n}{b}\) 是每个子问题的大小
- \(f(n)\) 是子问题合并成原问题所需的代价
分三种情况：
- $ f(n) < n^{\log_b ^a} $ ，那么 $T(n) = \varTheta (n^{\log_b ^a}) $
- $ f(n) = n^{\log_b ^a} $ ，那么 \(T(n) = \varTheta (n^{\log_b ^a}\log n)\)
- $ f(n) > n^{\log_b ^a} $，那么 \(T(n) = \varTheta (f(n))\)
摊还分析
求数据结构的一系列操作的平均时间。可以保证某一系列操作在最坏情况下的平均性能
聚合分析
确定 $ n $ 个操作的最坏复杂度 \(T(n)\) ，每一个操作的平均代价就是 \(\frac{T(n)}{n}\)
核算法
对不同操作赋予不同的费用，称其为摊还代价。当一个操作的摊还代价大于实际代价的时候，将差额存起来，称为存款，后续操作如果有摊还代价小于实际代价时，我们将之前存的信用拿出一部分来抵消这里的差值。
摊还代价不是随便取的，要构造一个摊还代价使得上面的存款不会被取完
势能法
将数据结构和势能关联起来
啥啊这是
标签：摊还,log,复杂度,时间,操作,代价,varTheta From： https://www.cnblogs.com/jingyu0929/p/17540147.html