看似错误的复杂度的渐近处理

堆的建立 \(\Theta(nlogn)\)

当我们试图将n个数简称堆时，一般认为将所有数暴力加入堆，一次复杂度\(\Theta(logn)\)，总复杂度为\(\Theta(nlogn)\)，事实上，其渐近复杂度为\(\Theta(n)\) 设\(\Theta(h)\)表示高度为h的数加入堆的复杂度 总代价为 $$\sum_{h=0}^{\lfloor logn\rfloor}\lceil \frac{n}{2^{h+1}} \rceil\Theta(h)=\Theta(n\sum_{h=0}^{\lfloor logn\rfloor}\frac{h}{2^{h}}) \ 又\because 根据等比数列求和，\sum_{h=0}^{n}\frac{h}{2^{h}}=2-\frac{1}{2^{n-1}}-n\frac{1}{2^n}\ \therefore \sum_{h=0}^{n}\frac{h}{2^{h}}=2(n->+\infty) \therefore \Theta(2n) $$

开平方 & 取对数

这两种操作一般不超过10，为常数级别

例：线段树维护区间所有数开平方，因为开6次以内就能得到1或0，所以复杂度\(\Theta(6nlogn)\),而不是\(\Theta(mnlogn)\)

阶乘 & 质数连乘

这两种操作一般不超过10，为常数级别

例：对于两个集合，只要其中两个数有>=p的质因数，则合并两个集合，问[a,b]内共有多少集合。因为一个数最多有6个质因数，所以复杂度\(\Theta(6n)\),而不是\(\Theta(n^2)\)