知识卡片
k有序只约束窗口均值
k 有序数组要求每个长度 k 的滑动窗口均值不大于紧邻的下一个窗口均值,而非每对相邻元素都有序。相邻窗口的 k−1 个共有元素抵消后,条件等价于 A[i]≤A[i+k];k=1 时才是通常的整体升序。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第8章 线性时间排序 · 查看原书依据
we call an n-element array A k-sorted if, for all i = 1, 2,
参考来源
- 位置:《算法导论(第4版)》第 8 章问题 8-5(`OEBPS/chapter008.xhtml`,文本字符 [32000, 35500);Art_P336)。
- 结论依据:原书 Art_P336 定义 (Σ_{j=i}^{i+k−1}A[j])/k ≤ (Σ_{j=i+1}^{i+k}A[j])/k;共有的 k−1 项抵消,得 A[i]≤A[i+k]。等价关系是问题 8-5(c) 要求证明的推导,非原书已给结论。
- 原始内容:we call an n -element array A k-sorted if, for all i = 1, 2, … , n – k