知识卡片

普通读书笔记卡 · 3619

k有序只约束窗口均值

理解等级:中级

k 有序数组要求每个长度 k 的滑动窗口均值不大于紧邻的下一个窗口均值,而非每对相邻元素都有序。相邻窗口的 k−1 个共有元素抵消后,条件等价于 A[i]≤A[i+k];k=1 时才是通常的整体升序。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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