math - n^O(1) が多項式時間を意味するのはなぜですか?

Question

ある k に対して実行時間が O(n ^k ) の場合、アルゴリズムは多項式時間で実行されます。^{ただし、時間 n O(1)}として定義された多項式時間も見ました。

これについていくつか質問があります。

1. なぜ n ^O(1)多項式時間なのですか? kさんはどうしたの？
2. n ^O(1)が多項式時間の場合、3n ²は n ^O(1)になります。しかし、3はどこに行ったのですか？それはどのように機能しますか？

ありがとう！

Answer 1

^{「ランタイムは O(n)」または「ランタイムは O(n 2} ) 」のような表現がある場合、O(n) および O(n ² ) の用語は実際の関数ではありません。代わりに、いくつかのプロパティを持つ他の関数のプレースホルダーです。たとえば、次のステートメントを考えてみましょう。

アルゴリズムの実行時間は O(n)

この発言の本当の意味は

アルゴリズムの実行時間が f(n) であり、f(n) = O(n) である関数 f(n) があります。

たとえば、関数の実際の実行時間が 137n + 42 の場合、「アルゴリズムの実行時間は O(n) です」というステートメントは真です。アルゴリズムは f(n) および f(n) = O(n) です。

^{これを踏まえて、「アルゴリズムの実行時間は n O(1)}です」というステートメントが何を意味するかを考えてみましょう。このステートメントは、

アルゴリズムのランタイムが n ^f(n)および f(n) = O(1)である関数 f(n) があります。

用語がより明確になったので、これは正確には何を意味するのでしょうか? 直観的には、関数が何らかの定数によって上から最終的に制限されている場合、その関数は O(1) です。したがって、O(1) である関数 f(n) は、n が十分に大きくなると、f(n) ≤ k を満たす必要があります。したがって、少なくとも直観的には、n ^O(1)は「n を最大でも k のべき乗にする」ことを意味し、これは多項式関数の定義のように聞こえます。

もちろん、一定の要因というやっかいな問題があります。関数 137n ³は間違いなく O(n ³ ) ですが、前に巨大な定数項があります。一方、 n ^{O(1)の形の関数がある場合、 n 3}の前に定数項はありません。これをどのように処理しますか？

これは、数学でかわいくできるところです。137n ³の場合、n > 1 のとき、

137n ³ = n ^{log _n 137} n ³ = n ^{3 + log _n 137}

_{これは n を log n} 137で累乗したものであることに注意してください。関数 log _n 137 は n が大きくなるにつれて大きくなるように見えるかもしれませんが、実際には逆の動作をし、n が大きくなると減少します。この理由は、基本式の変更を使用して log _n 137 を次のように書き換えることができるためです。

ログ_n 137 = ログ 137 / ログ n

log n が減少すると、長期的には明らかに減少します。したがって、式 3 + log _n 137 は、何らかの定数によって上から制限されることになり、O(1) になります。

この手法を使用すると、n の指数を k に定数係数の対数底 n を加えたものを選択することで、O(n ^k )^をn ^O(1)に変換できます。 ●○表記。同様に、 n の指数の O(1) 項によって隠されている関数の上限を定める任意の定数として k を選択することにより、n ^O(1)から O(n ^k )に戻すことができます。

お役に立てれば！