YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Japanese subtitles

← 02-09 Big-Theta

Get Embed Code
2 Languages

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

  1. 前回の格子グラフの分析では
  2. エッジの数の計算式として最終的に得られたのは
    2n-2√nでした
  3. 何ともやっかいな関数ですが実のところ
  4. こうした分析が複雑になるほど
  5. 得られる解答もこのように扱いにくくなっていきます
  6. 研究者はもっと高度な形で
    関数を説明する方法を考え出しました
  7. やはり難解なものですが
    細部にとらわれずに扱えるようになります
  8. 漸近的成長という概念です
  9. それはビッグ・オー記法などの形で表されています
  10. ただし先にビッグ・シータ記法から説明しましょう
  11. Θ(g(n))とは関数の集合を表しています
  12. 具体的にはg(n)と等しい速さで成長するという関数です
  13. もう少し正確に説明します
  14. ある関数f(n)が
    g(n)と成長率の等しい関数の集合に属する
  15. その必要十分条件は
    定数c₁、c₂およびある閾値n₀について
  16. n₀より大きなすべてのnにおいて
  17. この大きな値nのすべてに対する関数f(n)は
  18. c₁g(n)≦f(n)≦c₂g(n)となるということです
  19. この概念を図で説明します
  20. ある関数f(n)を考えましょう
    nが増加するとf(n)も増加します
  21. さらにある関数g(n)にc₁をかけたものと
  22. より大きなc₂をかけたものもあります
  23. 図に示されているように閾値n₀の右側に出ると
  24. f(n)は常にc₂g(n)とc₁g(n)の間にあることが
    分かります
  25. 始まりは不可解かもしれませんが漸近的に成長して
  26. 十分大きな極限になると
    f(n)はc₁g(n)とc₂g(n)の間にあるのです
  27. それが成り立ちそうしたc₁、c₂、n₀が存在するなら
    f(n)はΘ(g(n))に属すると言えます