温故知新 —— Sliding Window

简介: 滑动窗口算法可以将嵌套的循环问题,转换为单循环问题,降低时间复杂度。

image.png

滑动窗口算法



滑动窗口算法可以将嵌套的循环问题,转换为单循环问题,降低时间复杂度。


比如给定如下数组:

[ 5, 7, 1, 4, 3, 6, 2, 9, 2 ]


求出 5 个连续元素的最大和是多少?


[5, 7, 1, 4, 3] 是第一组 5 个连续元素,求和是 20[7, 1, 4, 3, 6] 是第二组 5 个连续元素,求和是 21......这样一直进行下去,最终对比发现 5 个连续元素的最大和是 24,由 [4, 3, 6, 2, 9] 组成;


简单粗暴的双层 for 循环算法实现:


const getMaxSumOfFiveContiguousElements = (arr) => {
  let maxSum = -Infinity;
  let currSum;
  for (let i = 0; i <= arr.length - 5; i++) {
    currSum = 0;
    for (let j = i; j < i + 5; j++) {
      currSum += arr[j];
    }
    maxSum = Math.max(maxSum, currSum);
  }
  return maxSum;
};


时间复杂度是 O(n*k),遍历情况如图示:

image.png


而通过滑动窗口算法,我们能将时间复杂度降低为 O(n)


我们将 5 个连续的元素放入一个窗口内,每做一次求和计算后,将窗口内的第一个数字减掉,然后再加上窗口外的后第一个数字,形成新的窗口,窗口长度不变,这样一直操作下去,直到窗口遍历完全部元素,结束遍历;

image.png


算法如下:

const getLargestSumOfFiveConsecutiveElements = (arr) => {
  let currSum = getSum(arr, 0, 4);
  let largestSum = currSum;
  for (let i = 1; i <= arr.length - 5; i++) {
    currSum -= arr[i - 1]; // subtract element to the left of curr window
    currSum += arr[i + 4]; // add last element in curr window
    largestSum = Math.max(largestSum, currSum);
  }
  return largestSum;
};
const getSum = (arr, start, end) => {
  let sum = 0;
  for (let i = start; i <= end; i++) {
    sum += arr[i];
  }
  return sum;
};


遍历图示:

image.png


通过 +1-1 的方式实现遍历,将双循环变成单循环,降低时间复杂度,这正是滑动窗口的技术要点;


当然,滑动窗口还有很多变形,比如长度不固定、滑动距离不是 1 ......

以上温故了滑动窗口的算法部分,接下来温故所学的 TCP 滑动窗口原理:


TCP 滑动窗口原理



起初,为了保证发送方与接收方之间,每个包都能被收到。并且是按次序的,发送过程是:

image.png

但是,这样又太慢了,于是升级为多个并行发送,加大吞吐量:

image.png

后来,为了实现“无序”发送,即做到:发送方拿到确认包 1 的时候,就发送包 3,而不是非要等拿到确认包 2 才能发包 3;


于是乎,滑动窗口粉墨登场;

image.png

窗口分为:已发送(未Ack)待发送(未Ack)两个部分,当已发送被 Ack 确认后,则发生窗口移动,将未发送的包划到待发送中去,这样一直移动下去,直至所有包发送完毕;针对丢包情况,滑动窗口有超时重传机制;

滑动窗口的最大优势在于:接收端可以根据自己的状况通告窗口大小,从而控制发送端的接收,进行流量控制


本篇温故算是小引,后续会带来更多关于滑动窗口的变形算法或应用~

我是掘金安东尼,公众号同名,输出暴露输入,技术洞见生活,下次再会~~


相关文章
|
算法
poj 2823 Sliding Window
让你设计一个队列,是其求里面最大值的时间复杂度尽可能的低,但这个队列除了最大值外,就是一个普通的队列,该怎么进出还是怎么进出,并不是优先队列。
46 0
window.scrollTop 不生效的原因,如何解决
window.scrollTop 不生效的原因,如何解决
515 0
|
存储 Android开发 iOS开发
Flutter(十四)——动画的原理以及Tween与Curve的使用
Flutter(十四)——动画的原理以及Tween与Curve的使用
690 1
Flutter(十四)——动画的原理以及Tween与Curve的使用
LeetCode 239. Sliding Window Maximum
给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。 返回滑动窗口最大值。
61 0
LeetCode 239. Sliding Window Maximum
|
算法 测试技术 计算机视觉
Py之slidingwindow&sliding_window:slidingwindow、sliding_window的简介、安装、使用方法之详细攻略
Py之slidingwindow&sliding_window:slidingwindow、sliding_window的简介、安装、使用方法之详细攻略
Py之slidingwindow&sliding_window:slidingwindow、sliding_window的简介、安装、使用方法之详细攻略
|
存储 Java Android开发
Window十二问(快扶我起来,我还能问)
关于Window,你了解多少呢?看看下面这些问题你都能答上来吗。
168 0
Window十二问(快扶我起来,我还能问)
为什么会有window.window这种设计
为啥要搞这个这个看起来貌似很奇葩的设计。 要解答这个问题,还得请出this,我们经常说浏览器中的全局对象是window, 这句话对了,也还没完全对。 全局对象的真实身份应该是全局作用域的this。 window只是为了便于访问this,弄出来的一个属性。
310 0
为什么会有window.window这种设计
|
Ubuntu 网络协议 安全
x window的奥秘
x window的奥秘
315 0
Silverlight & Blend动画设计系列十三:三角函数(Trigonometry)动画之飘落的雪花(Falling Snow)
原文:Silverlight & Blend动画设计系列十三:三角函数(Trigonometry)动画之飘落的雪花(Falling Snow)   平时我们所看到的雪花(Falling Snow)飘飘的效果实际上也是一个动画,是由许多的动画对象共同完成的一个界面效果。
962 0
|
C#
WPF Touch操作滚动条,Window弹跳
原文:WPF Touch操作滚动条,Window弹跳 WPF,用ScrollViewer控件,触屏开发,当滑动到最后时会使整个窗体弹跳一下 原因是因为ScrollViewer触屏操作原生支持惯性,ScrollViewer中的内容滚动到边界是会自动触发Window Bounce(窗体弹跳), 以叫做Panning Feedback(拖动回馈)。
1174 0