Subsections
データの数が
![$ N$](img5.png)
個の場合,サーチの計算回数を考えよう.もっともバランス良く,ツリー
構造ができたとする.その深さを
![$ m$](img6.png)
とすると,
![$\displaystyle \sum_{n=1}^{m-1} 2^{n-1}\leq N=1+2+4+8+\cdots\leq\sum_{n=1}^{m} 2^{n-1}$](img7.png) |
(1) |
が成り立つ.これから,
![$\displaystyle 2^{m-1}-1 \leq N \leq 2^{m}-1$](img8.png) |
(2) |
となる.これから,深さ
![$ m$](img6.png)
は
![$\displaystyle m-1 \leq \log_2(N+1) \leq m$](img9.png) |
(3) |
を満たす整数となる.サーチの回数はツリーの深さと同程度であることが直感的に分かる
だろう.従って,データ数
![$ N$](img5.png)
が大きい場合,その計算回数(比較回数)は
![$ O(\log_2 N)$](img10.png)
と
なることが分かるだろう.
バランスが悪い木(教科書 Fig 6-19右図)の場合の,比較の回数は平均で
回である.
従って,計算量は
となる.
データ量が非常に多い場合,すなわち
が非常に大きい場合,この計算量の差は顕著な
者となる.したがって,バランスの良いツリー構造を作らなくてはならないことが分かるだろう.
教科書を使って,説明する.
教科書を使って説明する.
ホームページ:
Yamamoto's laboratory著者:
山本昌志
Yamamoto Masashi
2006-01-30