0

Hashtbl.create の複雑さは O(nlogn) であるとどこかで読みました。

Hashtbl は配列として実装されており、Array.create は O(n) の複雑さを持っているため、奇妙だと思いました。だから私はソースコードを調べました：

let rec power_2_above x n =
    if x >= n then x
    else if x * 2 > Sys.max_array_length then x
    else power_2_above (x * 2) n

let create ?(random = !randomized) initial_size =
    let s = power_2_above 16 initial_size in
    let seed = if random then Random.State.bits (Lazy.force prng) else 0 in
    { initial_size = s; size = 0; seed = seed; data = Array.make s Empty }

最初に *initial_size* を超える最小の 2 乗を見つけ、それから配列を作成します。これは O(n logn) のようには聞こえません... O(2**(logn +1)) のようなものを考えています。

何か案は？

ありがとう。

4

1 に答える 1

1

あなたの例ではどういうn意味ですか？配列の場合、その作成は配列の要素数であるO(n)と言います。nハッシュテーブルの場合、 sizeO(n)で初期化された基になる配列がありますが、nここでは、ハッシュ テーブルの (将来の) 要素数には関係なく、初期サイズ パラメータにのみ関係します。

いつでもサイズ1や好きな定数を渡すことができ、ハッシュテーブルのサイズをより頻繁に変更する必要があります。これはコストがかかりますが、償却された操作です: 途方もなく小さい初期サイズは、実行時間の定数乗法係数にのみ影響し、実行時間には影響しません。そのアルゴリズムの複雑さ。初期サイズが途方もなく大きいと、時間とメモリに膨大な一定のオーバーヘッドが発生します (32 ビット アーキテクチャや十分なメモリがない場合は失敗する可能性があります)。

于 2013-01-06T14:38:09.497 に答える