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元素的数量。在哈希表的情况下，有一个初始化为 size 的底层数组O(n)，但n这里与哈希表的（未来）元素数量无关，仅与初始大小参数有关。

您可能总是传递大小1或您喜欢的任何常数，并且哈希表将不得不更频繁地调整大小，这是一个昂贵但摊销的操作：一个可笑的小初始大小只会影响您运行时间的常数乘法因子，而不是其算法复杂度。一个大得离谱的初始大小会在时间和内存上造成巨大的持续开销（并且可能在 32 位架构上失败，或者如果您没有足够的内存）。

于 2013-01-06T14:38:09.497 回答