algorithm - 関数のbig-Oは何ですか (log n)^k

Question

任意の k に対する関数 (log n) ^kの big-O 複雑度は?

Answer 1

実行時の形式が (log n) ^kである関数は、 O((log n) ^k ) です。この式は、単純な変換を使用して他のプリミティブ関数に還元することはできず、O(n (log n) ² ) のようなランタイムを使用するアルゴリズムを見るのはかなり一般的です。この成長率を持つ関数は、多対数関数と呼ばれます。

ちなみに、通常 (log n) ^{kは log k} nと書かれているので、上記のアルゴリズムの実行時間は O(n log ² n です。あなたの場合、関数 log ² n + log n は O(log ² n ）。

ただし、k が定数であると仮定すると、 log (n ^{k ) の形式の実行時間を持つすべての関数の実行時間は O(log n) になります。}これは、対数恒等式を使用して log (n ^k ) = k log n であり、k が定数であるため k log n が O(log n) であるためです。^{ただし、O(log (n k} ))であるアルゴリズムが O(log n) であると盲目的に結論付けないように注意する必要があります。k が関数のパラメーターであるか、n に依存している場合、この場合の正しい big-O 計算は O(k log n) になります。

作業しているコンテキストによっては、定数 k のO(f(n) log ^{k n) を意味する Õ(f(n)) という表記を目にすることがあります。}これは " soft-O " と呼ばれることもあり、対数項が関係ないコンテキストで使用されます。その場合、両方の関数が Õ(1) であると言えますが、この使用法は単純なアルゴリズム分析では一般的ではありません (実際、ウィキペディア以外で、これが正確に 1 回使用されているのを見たことがあります)。

お役に立てれば！

Answer 2

それはまだです(log(n))^2。累乗された対数は、すでに最小/最も単純な形式になっています。

Answer 3

(log n)^k は:

• O((log n)^k)
• O(n^k)
• の上）
• O(n log n)
• O(n^1/2)
• O(n^0.00000002)

どれがあなたにとって意味があるかは、定数とコンテキストによって異なります。

Answer 4

log(n)O((log(n))^2)式全体がO((log(n))^2)