Frank Yellin

当他们说 O(1) ,意思是“摊余成本”。有些手术可能更昂贵,但手术的平均成本仍然很低 O(1) .

我最初的答案如下。我意识到我的证明可以大大简化。

假设当前数组大小为 P = 2^n .一些元素 k 已从上一个数组复制到此数组中。每次复制时,我们复制的元素数量是上一次复制时的两倍。所以移动的元素总数是 k + k/2 + k/4 + ... 这比 2k 这比 2P .

如果我们表演过 N 操作时,数组的大小小于 2N ,我们的表现还不到 4N 副本。因此,副本数量为 O(N) .QED

请注意,我从未在证明中使用过2/3。我们唯一需要的是,每个副本的大小是前一个副本的两倍,并且数组大小与操作数成正比。

这是我最初的答案。

让我们假设在数组已满3/4时复制。这个想法还是一样的,但我们可以用整数。我们从大小为8到16的数组中复制6个元素。我们将12个元素复制到大小为32的数组中。我们将24个元素复制到大小为64的数组中。

[我在用 ^ 指指数,而非排他性或

所以我们最终复制了 6(1 + 2 + 4 + ... 2^n) 元素组成一个数组 2^(n + 3) .但第一个数字小于 6 * 2^(n + 1) 这就是 1.5 * 2^(n * 3) 。因此,无论我们当前使用的是什么大小的数组,到达该数组的复制总量都不到该数组大小的1.5倍。

我不知道这是否是你的问题的原因,但你的代码有六次调用 np.empty .我看不到这些阵列以后会进行任何初始化。

NP空的 导致数组未初始化,内存将包含随机垃圾。试着用 np.zeros 看看你是否能得到更好的结果。

如果你打字

cast(type, value1)

那么结果将与 value ,但您已经告诉类型检查器,它的类型就是指定的类型,并且它只需要相信您。

从文件中:

typing.cast(typ, val)

将值强制转换为类型。

这将返回不变的值。向类型检查器发送此信号 返回值具有指定的类型,但在运行时 故意不检查任何东西(我们希望它尽可能快 可能)。