algorithm - 摊销复杂度和最坏情况时间复杂度之间的联系

Question

我有一组 n 个连续操作，每个操作都以 O(1) 摊销复杂度运行。我可以说整个集合以 O(n) 最坏情况时间复杂度运行吗？我该如何证明呢？

Answer 1

您没有提供代码示例，因此我将n 连续操作视为算法 for 循环。所以任务是估计最坏情况的复杂度

for(int i=1; i<n; i++)
{
   f(x) // O(f(x)) = O(1)
}

换句话说

Sum(1,n) 1 = O(1) + O(1) + ... O(1) //n-times

或者

O(1) + O(1) + ... O(1) = O(n)O(1) = O(n)