O(1)というのはご機嫌に速いということ?

「実際に起こりうる状況ではご機嫌に速い」という意味で「O(1)」と書くことがあるわけですが、誤解が生じるのでやめたほうがいいと思います。

たとえばn桁の足し算は、2つの整数および結果が適当なレジスタに収まるうちは、1クロック(程度)でできるのでご機嫌に速いわけですが、O(1)というわけではもちろんなく、O(n)だと考えるのがふつうでしょう。

もう少し厳密に言うと、精度に限りがあるのであれば、指数関数もO(1)でよい、ということです(ベキ乗はO(1)でOK?

もう少し厳密に言えば、O記法は極限の概念の上に成り立っているものなので、精度に限りがあるときには使いません。精度に限りがあるのなら、結果の入ったテーブルを使うことで、どんな関数でもご機嫌に速く計算できます。もっとも、テーブルを作るのに時間がかかるわけですが、

こうして一度出した結果を覚えておいて、あればそれを使うという方法はメモ化(memoization)として知られています。見ての通り、定義通りなナイーブな計算法を使っているのに、O(2n)がO(1)(厳密には、最初の一回だけO(n))になってしまうのです。(フィボナッチ数列にO()を学ぶ

ということが許される状況でなら、まあ、いいのでしょう。もう少し厳密に言えば、O記法は「最初の1回だけ」というような場合には使いません。

追記:元サイトに載っているコードが正しい結果を返すのはn=70まで(Cだと再現性がないかもしれない。確かめたければJavaのStrictMathとかで)。そのくらいだと、もっともナイーブな実装でなければ、テーブルを作るのもそれを覚えてのも簡単。計算量や計算時間について真剣に考えるものではないのかも。

補足:カジュアルなO記法

2 thoughts on “O(1)というのはご機嫌に速いということ?

  1. 全然本文と関係ないんですけど,ご機嫌に速いって表現,日本語にあるんですか?
    どれくらい速いか見当がつかないんですけどw

  2. ネーミングのセンスを問われているわけですね
    カジュアルに言えば、
    ある関数fがあって、f(1)よりf(1000)のほうが計算に時間がかかりそうに見えても、
    実際には同じ時間で計算できる
    ということになるのかなあ。
    「f(1)よりf(1000)が」というのは単なる例で、
    計算量が直感(あるいはナイーブな計算)に反していればいいのかも
    「intの足し算」は「ご機嫌に速い」のですが、「N桁の足し算」の計算量は「O(N)」です

コメントは停止中です。