这是一个家庭作业的问题。设A []是整数和整数k的阵列 - 窗口大小。生成阵出现在窗口的最小值并购，因为它滑过答：我发现一篇文章与该问题的解决方案，但不明白的为什么有O（n）的复杂性。任何人都可以解释给我？

This is a homework problem. Let A[] is an array of integers and integer K -- window size. Generate array M of minimums seen in a window as it slides over A. I found an article with a solution for this problem but did not understand why it has O(n) complexity. Can anybody explain it to me?

推荐答案

这往往抓住人们出来。你可能会认为它会采取 O（N ^ 2）时间，因为您的原因将需要 O（N）时间和你有 O（N）元素。然而，实现各元件只能添加一次并除去一次。因此，在总花费 O（N）滑过整个数组 A 。

This tends to catch people out. You would think it would take O(N^2) time since you reason adding takes O(N) time and you have O(N) elements. However, realise each element can only be added once and removed once. So in total it takes O(N) to slide over the whole array A.

这产生了的摊销效率O（1）您通过一个元素移动滑动窗口每次。换句话说，它需要由一个元件移动滑动窗口的平均时间是 O（1）

This yields an amortised efficiency of O(1) every time you move the sliding window on by one element. In other words, the average time it takes to move the sliding window by one element is O(1).