ホーム » 2008 » 4月 » 21

日別アーカイブ: 2008年4月21日

2008年4月
 12345
6789101112
13141516171819
20212223242526
27282930  

検索・リンク

オーダ記法と処理時間の見積り&再帰関数

先週の単純検索や最大選択法の処理時間の発展として、2分探索法の処理時間が、 IMG n /cgi-bin/mimetex.cgi?T(N)={T_a}+\log{N}\times{T_b} を示し、これらの処理速度の見積りでは、Nが大きくなったときの最大項しか 使わない点や、Nの式の部分が重要であることを確認し、オーダ記法を説明する。

オーダ記法では、Nが大きくなったときの最大項を抜粋し、係数は書かないことを示す。 簡単な時間式からオーダ記法を求めたり、時間予測の例題を示す。

時間があったので、次の再帰関数の時間見積りの例として、 再帰関数(fact,dango,fib)の実行予測を行い、再帰の処理の流れを復習。 fact,dango などが IMG n /cgi-bin/mimetex.cgi?T(N)={T_a}+{N}\times{T_b} であることを示す。

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー