big-o - （log n）^ k = O（n）？kが1以上の場合

Question

(log n)^k = O(n)? For k greater or equal to 1.

私の教授はクラスでこのステートメントを提示しましたが、関数がO（n）の時間計算量を持つことの意味がわかりません。のようなものでさえn^2 = O(n^2)、関数f（x）はどのようにして実行時の複雑さを持つことができますか？

ステートメントに関しては、O（（logn）^ k）ではなくO（n）とどのように等しいのでしょうか。

Answer 1

（log n）^ k = O（n）？

はい。fbig-Ohの定義は、正の定数Nとcが存在する場合、関数はO（g（n））にあり、すべてのn > N：f(n) <= c*g(n)。この場合f(n)は(log n)^kでg(n)ありn、であるため、これを定義に挿入すると、次のようになります。「定数Nとcが存在し、すべてに対してn > N：(log n)^k <= c*n」。これは真実(log n)^kであり、O（n）にも当てはまります。

関数f（x）の実行時の複雑さはどのようになりますか

そうではありません。big-Oh表記については、実行時の複雑さに固有のものはありません。Big-Ohは、関数の成長を分類するための表記法です。多くの場合、私たちが話している関数は特定のアルゴリズムの実行時間を測定しますが、big-Ohを使用して任意の関数について話すことができます。

Answer 2

f(x) = O(g(x))f(x)に遅くまたは同等に成長することを意味しg(x)ます。

技術的には、これは「過去のこのサイズがのスケーリングされたサイズよりも小さくなるようなx値x_0、、およびスケール係数を見つけることができる」と解釈されます。または数学で：Mf(x)x_0g(x)

|f(x)| < M |g(x)| for all x > x_0。

だからあなたの質問のために：

log(x)^k = O(x)?質問しています：そのようなx_0とMはあり ますかlog(x)^k < M x for all x>x_0。

そのような存在は、Mさまざまx_0な制限結果を使用して実行でき、L'Hopitalsルールを使用して比較的簡単です。ただし、微積分なしで実行できます。

---

ロピタルの定理に依存しない、私が思いつくことができる最も簡単な証明は、テイラー級数を使用します

e^z = 1 + z + z^2/2 + ... = sum z^m / m!

使用z = (N! x)^(1/N)すると、それを見ることができます

e^(x^(1/N)) = 1 + (N! x)^(1/N) + (N! x)^(2/N)/2 + ... (N! x)^(N/N)/N! + ...

x> 0の場合、すべての項は正であるため、N番目の項のみを保持すると次のようになります。

e^((N! x)^(1/N)) = N! x / N! + (...) 
                 = x + (...)
                 > x  for x > 0

両側の対数を取り（対数は単調に増加するため）、次にN乗に上げます（N> 0から単調に増加します）

(N! x)^(1/N) > log x  for x > 0
N! x > (log x)^n      for x > 0

これはまさに私たちが必要とする結果です(log x)^N < M x。Mx > x_0M = N!x_0=0