n=0Nlog(n)\sum_{n=0}^{N}\log(n) の計算量は Nlog(N)N\log(N)

Published at: 2021/05/16

例えば、個数 NN の平衡木を構築する場合、その計算量は O(n=1Nlog(n))\mathcal{O}(\sum_{n=1}^{N}\log(n)) になるが、これの具体的な計算量は何になるのか、という話。

n=1Nlog(n)=log(N!)\sum_{n=1}^{N}\log(n) = \log(N!)

であり、 log(N!)\log(N!)スターリングの公式により、 Nlog(N)N\log(N) が主要項であることが示される。

なので、

O(n=1Nlog(n))=O(Nlog(N))\mathcal{O}(\sum_{n=1}^{N}\log(n)) = \mathcal{O}(N\log(N))

tags: 数学計算量