math - 再発を解決する

Question

T（n）= T（n-1）+lgn私のアプローチは次のとおりです。

n-1、n-2、n-3を代入すると、最後に、T（n）= T（1）+ lg 2 + lg 3となり、lg n => T（n）= lg（2 * 3 * 4 * 5 n）したがって、T（n）= lg（n！）。

しかし、彼らはnlgnとして答えを与えます。

Answer 1

これは計算の複雑さの問題ですか？もしそうなら、あなたと「彼ら」の両方が正しいです。

O(lg(n!)) = O(lg(n^n)) = O(n lg(n))

より厳密に、スターリングの公式から：

lg(n!) = n lg(n) - n + O(ln(n))

したがって

O(lg(n!)) = O(n lg(n)) + O(n) + O(ln(n)) = O(n lg(n))