我知道将一个元素插入数组需要一个常数时间让我们说 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/