滑动 Window 算法

Question

我知道滑动window算法的时间复杂度是o(N)但是可变大小的滑动window算法的时间复杂度是多少

例如-

数组 = [1,2,3,4,5,6]

当滑动尺寸window = 1 window - [1]、[2]、[3]、[4]、[5]、[6]

当滑动尺寸window = 2 window - [1,2], [2,3], [3,4], [4,5], [5,6]

当滑动尺寸window = 3 window - [1,2,3], [2,3,4], [3,4,5], [4,5,6]

等等...

window 尺寸范围从 1 到 n（window 尺寸的有效值）。如果创建单个 window 花费 O(N) 那么创建 N windows 将花费 O(N^2)?

Answer 1

运行 无论 window.

的大小如何，跨数组的滑动 window 都是 O(n)

对于所有 window 大小，头指针和尾指针单调递增。相反，典型的嵌套循环二次算法对每个外部索引 i.

运行从 i 到 n 的内部索引 j

这里的假设是，除了双端队列报价和轮询（每个 i 的固定时间）之外，您没有做任何额外的工作，例如为每个 window 循环 i.

如果您要从 1 到 n 创建 n windows，您将回到经典的嵌套循环二次算法，O(n^ 2).