通过改变大小增加动态数组时的分摊运行时间
Amortized Runtime When Increasing Dynamic Array by Varying Sizes
我有一个动态数组,我不断地向其追加项目。附加是复杂性 O(1)
。当数组变满时,我想将数组增长并复制过来,这很复杂O(n)
。
现在,假设我在数组变满时以不同的速率增长它。这些比率是:
i) 一些常量 C
ii) n/2
iii) n^2
每种情况下的分摊运行时间是多少?
我相信我能够破案 i
。摊销运行时间将是操作的总成本除以操作总数。在这种情况下,总成本为 C * O(1) + 1 * O(n)
,总操作次数为 C
。因此,摊销运行时间为 O(n)
.
然而,在分析剩下的两个案例时,我有点迷茫。在我看来,操作总数将分别为n/2 + 1
和n^2 + 1
,但我不太清楚如何计算操作的总成本。
谁能引导我走上正确的道路?
您可以使用与第一种情况类似的分析。
ii.
(n/2 * O(1) + O(n)) / (n/2) = O(1) + O(n)/n = O(1)
iii.
(n^2 * O(1) + O(n)) / (n^2) = O(1) + O(n)/n^2 = O(1)
This answer 更详细地解释了为什么按 n
比例调整大小的动态数组(假设它调整到 n
1 的幂或更大)有一个常数摊销成本。
我有一个动态数组,我不断地向其追加项目。附加是复杂性 O(1)
。当数组变满时,我想将数组增长并复制过来,这很复杂O(n)
。
现在,假设我在数组变满时以不同的速率增长它。这些比率是:
i) 一些常量 C
ii) n/2
iii) n^2
每种情况下的分摊运行时间是多少?
我相信我能够破案 i
。摊销运行时间将是操作的总成本除以操作总数。在这种情况下,总成本为 C * O(1) + 1 * O(n)
,总操作次数为 C
。因此,摊销运行时间为 O(n)
.
然而,在分析剩下的两个案例时,我有点迷茫。在我看来,操作总数将分别为n/2 + 1
和n^2 + 1
,但我不太清楚如何计算操作的总成本。
谁能引导我走上正确的道路?
您可以使用与第一种情况类似的分析。
ii.
(n/2 * O(1) + O(n)) / (n/2) = O(1) + O(n)/n = O(1)
iii.
(n^2 * O(1) + O(n)) / (n^2) = O(1) + O(n)/n^2 = O(1)
This answer 更详细地解释了为什么按 n
比例调整大小的动态数组(假设它调整到 n
1 的幂或更大)有一个常数摊销成本。