滑动窗口算法
滑动窗口算法可以将嵌套的循环问题,转换为单循环问题,降低时间复杂度。
比如给定如下数组:
[ 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)
,遍历情况如图示:
而通过滑动窗口算法,我们能将时间复杂度降低为 O(n)
;
我们将 5 个连续的元素放入一个窗口内,每做一次求和计算后,将窗口内的第一个数字减掉,然后再加上窗口外的后第一个数字,形成新的窗口,窗口长度不变,这样一直操作下去,直到窗口遍历完全部元素,结束遍历;
算法如下:
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; };
遍历图示:
通过 +1
-1
的方式实现遍历,将双循环变成单循环,降低时间复杂度,这正是滑动窗口的技术要点;
当然,滑动窗口还有很多变形,比如长度不固定、滑动距离不是 1 ......
以上温故了滑动窗口的算法部分,接下来温故所学的 TCP 滑动窗口原理:
TCP 滑动窗口原理
起初,为了保证发送方与接收方之间,每个包都能被收到。并且是按次序的,发送过程是:
但是,这样又太慢了,于是升级为多个并行发送,加大吞吐量:
后来,为了实现“无序”发送,即做到:发送方拿到确认包 1 的时候,就发送包 3,而不是非要等拿到确认包 2 才能发包 3;
于是乎,滑动窗口粉墨登场;
窗口分为:已发送(未Ack)
和待发送(未Ack)
两个部分,当已发送被 Ack 确认后,则发生窗口移动,将未发送
的包划到待发送
中去,这样一直移动下去,直至所有包发送完毕;针对丢包情况,滑动窗口有超时重传
机制;
滑动窗口的最大优势在于:接收端可以根据自己的状况通告窗口大小,从而控制发送端的接收,进行流量控制
。
本篇温故算是小引,后续会带来更多关于滑动窗口的变形算法或应用~
我是掘金安东尼,公众号同名,输出暴露输入,技术洞见生活,下次再会~~