conj、cons などの基本的な clojure ライブラリ関数の Big-O の複雑さをリストしたリソースを誰か教えてもらえますか? 入力の種類によって Big-O が異なることはわかっていますが、そのようなリソースはありますか? どれくらい速く実行されるかについて大まかな考えを持たずに何かをコーディングするのは不快です。
質問する
2901 次
2 に答える
11
ここでのパーティーに遅れましたが、最初の回答のコメントのリンクがより決定的であることがわかったので、いくつかの変更を加えてここに再投稿します(つまり、english->big-o
):
ソートされていないコレクションでは、O(log 32 n) はほぼ一定の時間であり、2 32ノードがビット分割されたトライノードに収まるため、これはlog 32 2 32 = 6.4の最悪の場合の複雑さを意味します。ベクトルは、インデックスがキーであるトライでもあります。
並べ替えられたコレクションは、可能な場合はバイナリ検索を利用します。(はい、これらは両方とも技術的には O(log n) です。定数係数を含めるのは参考用です。)
リストは、最初の要素の操作に対して一定の時間を保証し、それ以外のすべてに対して O(n) を保証します。
于 2014-01-05T10:11:49.487 に答える