gpt4 book ai didi

c - 向数组末尾插入 n 个元素的时间复杂度是多少?

转载 作者:行者123 更新时间:2023-12-02 03:33:18 24 4
gpt4 key购买 nike

我知道将一个元素插入数组需要一个常数时间让我们说 c。

我尝试过的:

用于插入n个元素 time=c+c+c+.......n 次 =nc

我想问的是big O of n还是o(1)

最佳答案

是的,添加 n 元素需要 O(n) 时间,但添加单个项目不是 O(1)。它是摊销 O(1)。

任何给定的加法本身可能需要 O(n) 时间,因为当前数组的空间已被填满,因此必须将其复制到另一个更大的空间。

但是如果新的空间分配是一个大于原始空间的一个的常数因子(通常使用 2),那么副本的成本会分摊,这样每次添加的平均时间就像你说的那样是常数,和 n 添加是 O(n)。

为了使这一点更清楚,考虑因子为 2 且初始数组大小为 1 的情况。然后考虑将数组从大小 1 增长到足以容纳 2^k+1 个元素的复制成本k>=0。这个大小是2^(k+1)。总复制成本将包括以 2 倍的步骤变得如此大的所有复制:

1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1 = 2n - 1

等式源于基本代数。结果是 O(n)。但是,最后一个副本本身有n = 2^k个元素,也是O(n)。

关于c - 向数组末尾插入 n 个元素的时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51175867/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com