Japanese 字幕

← 02-12 Big-Theta Examples

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

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

  1. ビッグ・シータを使うと
    複雑な関数を簡潔に書き表すことができます
  2. 1/2(n²)という関数ならΘ(n²)で考え
  3. 8√nならΘ(√n)で考えられます
  4. 前に出てきた2n-2√nという式ならΘ(n)です
  5. これは漸近的には線形関数です
  6. 一方このn⁴を含んだ複雑な式は
  7. 非常に速く成長しますがΘ(n⁴)と表せます
  8. nの自然対数 ただし実際にはどの底のlog nでも
  9. 底が定数であるならΘ(log n)です
  10. 私はコンピュータ科学者なので
    底が2の対数で考えることが多いですね
  11. π²はnと共に成長せず
    最後には集合Θ(1)の要素となります
  12. これも単なる定数です
  13. もう少しだけビッグ・シータの定義を使って
  14. 格子グラフのエッジの数を計算する2n-2√nが
  15. Θ(n)のように成長する線形関数であることを
    示したいと思います
  16. そのためにはゼロより大きな定数c₁、c₂と
    閾値n₀を見つける必要がありますが
  17. その時n₀より大きなすべてのnで
    この関数はこの2つのスケーリングの間にあります
  18. まずこちらを見ましょう
  19. c₂が入っている理由は
    この式より確実に大きくするためです
  20. 分かりやすいように
    この不等式を反対に書いてみると
  21. c₂nの方が大きいのでこうなります
    そしてnで割ります
  22. するとc₂の値は
    2からこの増加する値を引いたもの以上となります
  23. 2ならうまくいくはずです
  24. c₂を2とするとこの式を満たします
  25. 以上の内容をまとめると
  26. c₂=2と設定できます
  27. ではc₁は1としましょう
  28. この関数の成長率は
    2nから2n未満の値を引いたものです
  29. するとnはそれ以下になります
  30. もしc₁が1なら
    nはこの式の値以下である必要があります
  31. それを満たすnの値は?
  32. いくつかの値は当てはまります
  33. 両辺において2√nを足してnを引きます
  34. さらに√nで割ると2≦n/√nとなり
    この値は√nとなります
  35. すると2≦√nです
  36. 両辺を2乗すると4≦nとなります 逆向きにすると
  37. もしn≧4ならこれが成り立ちます
  38. つまりnの小さな値を捨てる必要がありますが
    n₀を4とすればそれが可能です
  39. これが当てはまるのはnがn₀より大きい場合のみです
  40. これですべてを示すことができました
  41. 定数であるn₀、c₁、c₂をこのように設定すると
  42. 十分に大きなnにおいてこの複雑な式は
  43. 2つの簡単な線形関数の間にある つまりこれですね