Japanese 字幕

← 02-11 Big-Theta Reflexive

埋め込みコードを取得する
2言語

Showing Revision 1 created 03/11/2014 by Fran Ontanaya.

  1. テストに慣れている人なら
    理由はともかく推測できるでしょう
  2. 答えはこれです 理由を説明します
  3. もし関数f(n)がΘ(g(n))に属するなら
  4. 逆にg(n)もΘ(f(n))に属するという推論を
    確かめましょう
  5. そのためにはビッグ・シータの定義に戻ります
  6. 定義はこれです ゼロより大きい定数c₁、c₂があり
  7. さらに閾値n₀があり
    この時c₁g(n)≦f(n)≦c₂g(n)となる
  8. なおすべてのnは閾値n₀より大きいというものです
  9. これに基づいて考えていきます
    この式を正数であるc₁で割ってみると
  10. 新たにこのような不等式ができます
  11. 0≦g(n)≦1/c₁(f(n))となります
  12. 同じようにこの式をc₂で割りましょう
  13. すると1/c₂(f(n))≦g(n)となります
  14. この2つを組み合わせると
  15. 1/c₂(f(n))≦g(n)≦1/c₁(f(n))となります
  16. なお1/c₂、1/c₁が定数であることに注意してください
  17. するとこの1/c₂は単なる定数なので
    名前をc₁に置き換えられます
  18. 同様にこの1/c₁もc₂に置き換え可能です
  19. これはまさにビッグ・シータの定義なので
  20. g(n)はΘ(f(n))に属するというのが結論です