Math Battle [ 0299: アルゴリズムの性能評価 ]

[ 0299: アルゴリズムの性能評価 ]

[ 湯会老人 (Mentor) の出題 ]

同じ問題を解くのにもさまざまな計算方法 (アルゴリズム) があります。
以下の 5 つ (所要時間をデータ個数 n に応じてモデル化したもの)
を評価し、高速な順にならべて順序を答えてください。

これは Stanford University online training course (Algorithms)
の中で実際に出題されている問題です。

[ 大宙麗亜ちゃん (elementary school) の回答 ]

簡単かな？

これらがなんのアルゴリズムかを答えるのではなく n に適当な値を入れて
5 個の式を計算すればいいですから。

とりあえず n = 100 とし、あとは Wolfram|Alpha に計算してもらいました。結果は:

d < c < b < (a と e) はわかりましたが、
a と e はどう区別すればいいのでしょう？

[ 大宙乗児君 (junior high) のコメント ]

Wolfram|Alpha で (a) と (e) のグラフを描くと簡単にわかるよ。

[ 湯会老人のコメント ]

レイアちゃんが最初に試しに入れてみた n = 100 という値が
結果的に大きすぎたということ。

次は n = 5 にして「有意な差」 (significant difference) が出るかどうか
を確認してごらん。

[ 大宙麗亜ちゃんのやり直し ]

n=5 とした結果は:

d < c < b < a < e の順が正しいようですね。

やったー !!!

[ 0299: アルゴリズムの性能評価 ]