动态数组放置元素的时间复杂度
dynamic array's time complexity of putting an element
在一次笔试中，遇到这样一道题：
当一个动态数组满时，它会扩展到两倍space，就像2到4、16到32等。但是将一个元素放入数组的时间复杂度是多少？
我认为扩展space不应该考虑，所以我写了O(n)，但我不确定
答案是什么？
为了增加数组大小，您不能简单地 "add more to the end" 因为您更有可能得到 "segmentation fault" 类型的错误。因此，即使作为平均值，它需要 θ(1) 步，因为你有足够的 space，如果 O 表示法是 O(n)，因为你必须将旧数组复制到新的更大的数组（你为其分配了内存）并且应该采取 n 步骤......通常。另一方面，当然，您通常可以更快地复制数组，因为它只是来自连续 space 的内存副本，并且在最佳情况下应该是一步，即页面 (OS) 可以取整个数组。最后……从数学上讲，即使考虑到我们正在制作 n / (4096 * 2^10) (4 KB) 个步骤，它仍然意味着 O(n) 的复杂性。
这取决于提出的问题。
如果问题问的是一次插入所需的时间，那么答案是O(n)，因为big-O意味着"worst case."在最坏的情况下，你需要增加数组。增长一个数组需要分配一个更大的内存块（正如你所说的通常大 2 倍，但可能会使用其他大于 1 的因素）然后复制整个内容，即 n 个现有元素。在某些语言中，如 Java，额外的 space 也必须被初始化。
如果问题要求摊销时间，则答案为 O(1)。另一种说法是 n 次添加的成本是 O(n)。
怎么会这样？每次加法都是 O(n)，但其中 n 次加法也需要 O(n)。这就是摊销的美妙之处。为简单起见，假设数组从大小 1 开始，每次填满时增长 2 倍，因此我们总是复制 2 的幂元素。这意味着第一次增长的成本是 1，第二次是 2，等等。一般来说，增长到 n 个元素的总成本是 TC=1+2+4+...n。嗯，不难看出 TC = 2n-1。例如。如果 n = 8，则 TC=1+2+4+8=15=2*8-1。所以 TC 与 n 或 O(n) 成正比。
无论初始数组大小或增长因子如何，只要该因子大于 1，此分析都有效。
如果你的老师很好，他或她以模棱两可的方式问了这个问题，看看你是否可以讨论这两个答案。
在一次笔试中，遇到这样一道题：
当一个动态数组满时，它会扩展到两倍space，就像2到4、16到32等。但是将一个元素放入数组的时间复杂度是多少？
我认为扩展space不应该考虑，所以我写了O(n)，但我不确定
答案是什么？
为了增加数组大小，您不能简单地 "add more to the end" 因为您更有可能得到 "segmentation fault" 类型的错误。因此，即使作为平均值，它需要 θ(1) 步，因为你有足够的 space，如果 O 表示法是 O(n)，因为你必须将旧数组复制到新的更大的数组（你为其分配了内存）并且应该采取 n 步骤......通常。另一方面，当然，您通常可以更快地复制数组，因为它只是来自连续 space 的内存副本，并且在最佳情况下应该是一步，即页面 (OS) 可以取整个数组。最后……从数学上讲，即使考虑到我们正在制作 n / (4096 * 2^10) (4 KB) 个步骤，它仍然意味着 O(n) 的复杂性。
这取决于提出的问题。
如果问题问的是一次插入所需的时间，那么答案是O(n)，因为big-O意味着"worst case."在最坏的情况下，你需要增加数组。增长一个数组需要分配一个更大的内存块（正如你所说的通常大 2 倍，但可能会使用其他大于 1 的因素）然后复制整个内容，即 n 个现有元素。在某些语言中，如 Java，额外的 space 也必须被初始化。
如果问题要求摊销时间，则答案为 O(1)。另一种说法是 n 次添加的成本是 O(n)。
怎么会这样？每次加法都是 O(n)，但其中 n 次加法也需要 O(n)。这就是摊销的美妙之处。为简单起见，假设数组从大小 1 开始，每次填满时增长 2 倍，因此我们总是复制 2 的幂元素。这意味着第一次增长的成本是 1，第二次是 2，等等。一般来说，增长到 n 个元素的总成本是 TC=1+2+4+...n。嗯，不难看出 TC = 2n-1。例如。如果 n = 8，则 TC=1+2+4+8=15=2*8-1。所以 TC 与 n 或 O(n) 成正比。
无论初始数组大小或增长因子如何，只要该因子大于 1，此分析都有效。
如果你的老师很好，他或她以模棱两可的方式问了这个问题，看看你是否可以讨论这两个答案。