∑n=0Nlog(n)\sum_{n=0}^{N}\log(n)∑n=0Nlog(n) の計算量は Nlog(N)N\log(N)Nlog(N)Published at: 2021/05/16例えば、個数 $N$ の平衡木を構築する場合、その計算量は $\mathcal{O}(\sum_{n=1}^{N}\log(n))$ になるが、これの具体的な計算量は何になるのか、という話。$$ \sum_{n=1}^{N}\log(n) = \log(N!) $$であり、 $\log(N!)$ は スターリングの公式により、 $N\log…