滑动窗口

2016年，Cloudflare在部署HTTP/2时遇到了一个奇怪的问题：某个高优先级的大文件传输会阻塞所有其他请求，尽管HTTP/2已经实现了多路复用。问题的根源在于TCP的流量控制机制——所有流共享同一个滑动窗口，一个流的丢包会让整个连接停摆。 ...

给定一个长度为100万的数组和一个大小为k的滑动窗口，要求输出窗口每次移动后的最大值。最直观的做法是：对每个窗口位置，遍历窗口内的所有元素找出最大值——总的时间复杂度是$O(n \times k)$。当k接近n时，这退化成了$O(n^2)$。 ...

在一个长度为 100 万的数组中找出连续 k 个元素的最大和。最直观的思路是：对每个可能的起始位置，累加 k 个元素，记录最大值。这需要大约 100 万次循环，每次循环内部还要遍历 k 个元素——总的时间复杂度是 $O(n \times k)$。 ...

假设你面前有一组从小到大排好序的数字，需要找出其中任意两个数之和等于目标值的组合。最直观的想法是嵌套两层循环，逐一尝试所有配对——时间复杂度 $O(n^2)$，当数据量达到十万级别时，程序开始变得迟缓。 ...

2005年，卡内基梅隆大学的研究人员进行了一项有趣的实验。他们在校园网络的边缘路由器上部署了四种不同的限流算法，然后用真实流量和Blaster蠕虫攻击数据进行测试。结果令人意外：表现最差的算法错误率高达30%，而表现最好的算法错误率低于1%。 ...