1

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

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

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

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

ありがとう！

4

3 に答える 3

3

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

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

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

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

つまり、

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

つまり、最初に a と b を選び、次にlog n + bn = O(n log n) であることを示します。a と b に関係なく、big-O 記法の定義で機能する固定の c と n 0があることを示しようとしているのではなく、誰かが a と b をどのように選択しても、常にac と n 0を見つけることができます- おそらく a と b に依存します - c と n 0の選択を使用して、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 0のときはいつでも、log n + bn ≤ cn log n となるようなn 0と cがあることを証明してください。
  • あなた: そうですね！c = a + b と n 0 = 2を選んでみてください。
  • 別の人: おい、その通りだ! それはうまくいきます！

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

お役に立てれば！

于 2013-09-18T19:40:23.007 に答える
1

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

于 2013-09-18T14:47:09.930 に答える