アルゴリズム百選 - ベキ乗はO(1)でOK? : 404 Blog Not Found

2007年12月04日23:00 カテゴリアルゴリズム百選Math アルゴリズム百選 - ベキ乗はO(1)でOK? これ、Hyukiさんをはじめ多くの方が疑問に思っていらっしゃるようなので、いまのうちに答えておきましょう。blogで書く以上、書く順番は順不同で構わないのですし。 アルゴリズム百選 - フィボナッチ数列にO()を学ぶ - www.textfile.org フィボナッチ数列の一般項を求める式を使ったときってO(1)って言えるのだろうか？まずは、論より証拠、というわけで実測値をご覧下さい。Cでフィボナッチ数をO(n)アルゴリズムと公式を使ってそれぞれ100万回計算した時にかかった時間をプロットしたものです。最適化をかけていないものと-O3で最適化をかけたものと双方を計測しています。fib(73)まで計算したのは、doubleで整数で保っておける限界がそこまでだったので。ソースは本

[kilrey]

精度付き演算でビッグオーを使う場合、精度への依存の項を書かないと意味がない。

[webmarksjp]

programming

[sankaseki]

[!GTD::資料(いつか使う)]404 Blog Not Found:アルゴリズム百選 - ベキ乗はO(1)でOK?

[agw]

秀逸なコメント。

[kiririmode]

そういえばTAで受け持っている講義にも似た問題がでてた

[bull2]

うーん、微妙だ

[kkobayashi]

コメントのshiroさんに同意。オーダーは定性評価だから実行結果という定量評価で比較するのはちと違うのかも。でもアルゴリズムはスゴイ

[katzchang]

なんと雑な。コメント欄「精度を区切っちゃったらO記法の議論は成り立たないっすよ」

[ag-commerce]

これ、Hyukiさんをはじめ多くの方が疑問に思っていらっしゃるようなので、いまのうちに答えておきましょう。blogで書く以上、書く順番は順不同で構わないのですし。

[nanakoso]

べき乗の実用的な高速アルゴリズム。

[taniguchitomoya]

そもそもnやfib(n)の範囲が精度の問題で限られてるから定数時間ってことか？それってO(1)って言うのか？

[endo_5501]

なにその魔法

[smoking186]

これはひどい

[riywo]

やべぇすげぇ。ソースの細かい意味はわかんねぇけど、アルゴリズムがすごいってのはよく分かる。アルゴリズムは芸術品ですからね、パンピーには芸術って分かってもらえないけど。