Mic*_*ael 5 algorithm
这是一个家庭作业问题.设A []是整数数组和整数K - 窗口大小.当它在A上滑动时,生成在窗口中看到的最小值的数组M.我发现了一篇文章解决了这个问题,但是不明白为什么它有O(n)复杂度.任何人都可以向我解释一下吗？
JPv*_*rwe 9
这往往会把人赶出去.您可能认为需要O(N^2)时间,因为您需要花费O(N)时间并且您有O(N)元素.但是,实现每个元素只能添加一次并删除一次.所以总共需要O(N)滑过整个阵列A.
O(N^2)
O(N)
A
O(1)每次将滑动窗口移动一个元素时,这会产生摊销效率.换句话说,将滑动窗口移动一个元素所花费的平均时间是O(1).
O(1)
归档时间：
15 年，7 月 前
查看次数：
4425 次
最近记录：