所以想问一下动态数组算法中复制元素的渐近增长。
在动态数组算法中，数组每次充满时都会将大小加倍，并且应该添加一个新元素。当数组满时，包含N/2个元素，翻倍后，新数组的大小为2N。然后在复制的对象/值之后插入下一个元素。
我相信复制的元素数量的大 O 是 O(N/2)，但我是否还必须考虑数组翻倍的次数？
非常清楚，这是我的导师布置的问题，我一直在思考它，但我目前不确定是否/如何计算数组翻倍的次数，仅给出一个大小为 N 的数组。
最佳答案
I believed that the Big-Oh for the number of elements copied would be O(N/2), but would I also have to account for the times that the array has been doubled?
您正在寻找的可能是每个操作的复杂性和 amortized complexity 之间的区别.
特别是，在动态数组中插入的最坏时间复杂度确实是 O(N)，但摊销复杂度是 O(1)(因为对于 N 次插入，最多复制 2*N 个元素。
关于algorithm - 复制动态数组中元素的大 O，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41786310/