5

私は先週学校でフィボナッチ数列のn：番目の数を計算する関数を実装する任務を負いました。「サブ割り当て」は、関数O（n）の時間計算量を与えるために、累積（正しい変換ではない可能性があります）を使用して実装することでした。関数を作成しようとするまで（Int-> Integer）、これはすべて正常に機能しました。少し実験してみると、非常に大きな数の場合、時間計算量はO（n ^ 2）に近いことがわかりました。これは整数の実装が原因であるに違いないことに気づきました。これは、それがどのように機能するかについて少し興味をそそられます。私はいくつかのグーグル検索をしましたが、役に立つと思われるものは何も見つかりませんでした。それで、説明またはそれを完全に説明するリンクのいずれかを得ることを期待して皆さんに頼っています。

私のコード：

ackfib 0 = 0
ackfib 1 = 1        
ackfib n = loop n 1 0 1
    where
        loop n n1 n2 i 
            | i < n     = loop n (n1+n2) n1 (i+1)
            | i == n    = n1
            | i > n     = error "n must be greater than or equal to 0"

私はすべての答えに感謝しています

ヴィクトル

4

2 に答える 2

13

これは実際には Haskell とは何の関係もありません。フィボナッチ数が急速に指数関数的に増加するという事実の結果です。具体的には、n 番目のフィボナッチ数は約 (log 2 φ) n または約 0.48 n ビットで、φ は黄金比 (1 + sqrt 5) / 2 です。k ビット整数の加算には O(k) 時間がかかるため、O (n) 加算には実際には合計で O(n^2) の時間がかかります。これは、加算する数値の平均が O(n) ビットであるためです。

(執着する人への注意: 上記の大きな O は、実際には大きな Theta である必要があります。)

于 2010-09-26T15:46:19.780 に答える
7

Reid's answerに追加すると、アルゴリズムに O(N) 時間の複雑さがあるという事実は、実行のステップと見なされるものに依存します。これは、時間の複雑さに関する一般的な誤解です。時間の複雑さは常に実行時間に対応しているということです。

このステップで何を考慮するかは、問題をどの程度深く分析したいかによって異なります。ステップを Integer の 1 つの加算として定義すると、アキュムレータを使用したアルゴリズムは O(N) 時間で実行されます。ステップを 1 ワードの加算 (32 ビットまたは 64 ビットの加算) として定義すると、Reid が説明したように O(N^2) で実行されます。

複雑さの分析を実行時間に対応させたい場合は、2 つのプロセッサ ワードの追加など、実行時間が定数によって制限される実行ステップを使用する必要があります。整数は任意に大きくなる可能性があるため、整数の加算はそうで​​はありません。

于 2010-09-26T15:56:55.220 に答える