math - a と b に関係なく、log n + bn = O(n log n) を表示します

Question

Big-O の問題を理解するのに助けが必要です。私は概念を理解しており、すでにいくつかの練習問題を行っていますが、これには困惑しています。

ビッグ O の定義を使用してf(n)=anlogn+bn、O(nlogn). (a, b > 0)

定数 A または B が変更された場合、C と N も変更する必要があるため、C または N を見つける方法がわかりません。それとも、私はこれを間違った方法で見ていますか?

テストが迫っていますが、事前に理解しておきたいのです。

ありがとう！

Answer 1

次のようなステートメントを受け取った場合:

log n + bn = O(n log n) であることを証明してください

次のように考えることができます。

a と b の任意の選択について、log n + bn = O(n log n) であることを証明します。

つまり、

a と b の任意の選択に対して、任意の n ≥ n ₀に対して a log n + bn ≤ cn log n となるようなc と n ₀の選択があります。

つまり、最初に a と b を選び、次にlog n + bn = O(n log n) であることを示します。a と b に関係なく、big-O 記法の定義で機能する固定の c と n ₀があることを示しようとしているのではなく、誰かが a と b をどのように選択しても、常にac と n ₀を見つけることができます- おそらく a と b に依存します - c と n ₀の選択を使用して、log n + bn = O(n log n) となります。

この例でこれをどのように行うかを確認するために、役に立つかもしれない 1 つの観察は (ログが底 2 であると仮定して)、n ≥ 2 である限り 1 ≤ log n であるということです。したがって、次のように n を制限する限り、 n ≥ 2 であることがわかります。

an log n + bn ≤ an log n + bn log n = (a + b) n log n

_{これを考えると、 c と n 0}をどのように選択できるか分かりますか? _{n ≥ 2 となるように n を制限しているので、n 0} = 2を選択するのは理にかなっています。同様に、log n + bn ≤ (a + b) n log n であることを証明したばかりなので、c を選択できます。 = a + b。

この議論は、2 人の人間の間の対話と考えることができます。

• 別の人: 私は a と b を選びますが、それらが何であるかは教えません。
• あなた: ええと、わかりました。
• 他の誰か: n ≥ n ₀のときはいつでも、log n + bn ≤ cn log n となるようなn ₀と cがあることを証明してください。
• あなた: そうですね！c = a + b と n ₀ = 2を選んでみてください。
• 別の人: おい、その通りだ! それはうまくいきます！

ダイアログは、相手が a と b を選択するところから始まることに注意してください。_{そうすれば、c と n 0}の選択を調整して、主張が確実に成立するようにすることができます。最初にc と n ₀を選択しようとすると、それを壊す a と b を常に見つけることができます。

お役に立てれば！

Answer 2

AとBは定数なので、CとNで表現Aしても問題ありませんB。たとえば、C=A+BとN > 2Aは を証明するのに十分ですf(n) = O(n lg n)。