我知道滑动窗口算法的时间复杂度是 o（N），但是可变大小的滑动窗口算法的时间复杂度是多少。
对于 e-
数组 = [1,2,3,4,5,6]
当滑动窗口的大小为 = 1 时窗口-[1],[2],[3],[4],[5],[6]
当滑动窗口的大小为 = 2 时窗口-[1,2],[2,3],[3,4],[4,5],[5,6]
当滑动窗口的大小为 = 3 时窗口-[1,2,3],[2,3,4],[3,4,5],[4,5,6]
等等...
窗口大小的范围为 1 到 n（窗口大小的有效值）。如果创建单个窗口的成本为 O（N），则创建 N 个窗口的成本为 O（N ^ 2）？
1
在数组中运行滑动窗口是 O（n），而不管窗口的大小。
对于所有窗口大小，头指针和尾指针单调增加。相反，典型的嵌套循环二次算法为每个外部索引i运行内部索引j从i到n。
这里的假设是，除了 deque 优惠和投票（每个i的恒定时间）之外，您没有做任何额外的工作，例如为每个i循环遍历窗口。
如果你正在创建n窗口从1到n，你回到经典的嵌套循环二次算法，O（n ^ 2）。
本站系公益性非盈利分享网址，本文来自用户投稿，不代表边看边学立场，如若转载，请注明出处
评论列表（82条）