平均時間計算量と最大時間計算量とは？

平均時間計算量と最大時間計算量とはなんでしょうか（＞＜；）ヤフーで検索してもよい回答がみつからなくて；　理解しておきたいので是非詳しくおしえていただけないでしょうか？よろしくおねがいします。

No.1 回答者： rinkun 回答日時： 2008/01/15 17:55

クイックソートの例で言えば、単純な実装では平均的にはn*log(n)の演算時間で計算できるが、最悪時にはn^2の演算時間が掛かる。

アルゴリズムはどのデータでも同じ演算時間(計算量)で結果を出すとは限らない。どんなデータに対しても一定の時間で計算するアルゴリズムもあれば、データによって演算時間が大きく変わるアルゴリズムもある。平均時間計算量は色々なデータに対する演算時間の平均であり、最大時間計算量は最悪のデータに当たったときの演算時間である。

たぶん。

この回答へのお礼

回答ありがとうございます＞＜。たすかります＾＾

お礼日時：2008/01/17 08:58