代码之家 › 专栏 › 技术社区 › Michael

滑动窗口最小算法

algorithm

Michael · 技术社区 · 14 年前

这是一个家庭作业问题。设A[]是一个整数数组,整数K——窗口大小。生成在窗口中看到的最小值的数组M,当它在a上滑动时,我发现 an article 为什么? 它具有O(n)复杂度。有人能给我解释一下吗?

1 回复 | 直到 14 年前

JPvdMerwe 14 年前

这容易把人赶出去。你会认为这需要 O(N^2) O(N) 时间和你有 O(N) 元素。但是,要意识到每个元素只能添加一次,删除一次。所以总的来说在整个阵列上滑动 A .

O(1) 每次你移动滑动窗口一个元素。换句话说,将滑动窗口移动一个元素所需的平均时间是 O(一)

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前