知识卡片

普通读书笔记卡 · 6067.z.1

选择线性时间有划分前提

理解等级:高级

选择算法只递归目标所在分区。若每次近似对半,划分工作依次约N、N/2、N/4,几何和为O(N);若每次只排除一个元素,工作和可变成N+(N-1)+…,达到O(N²)。因此本书的线性分析依赖理想划分,不能作为任意枢轴策略的最坏情况保证。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      假设一种理想的情况,枢轴元素基本位于中间值,即它总是将原数组划分成两个大小基本相等的子数组S (1)和S (2)。 要求解第K 小的元素,有以下3种情况。 (1)若K < |S (1)|,则说明第K 小的元素位于S (1)子数组中。其中,|S (1)| 表示 S (1)

    参考来源

    - 位置:《代码精进之路:从码农到工匠(异步图书)》9.1.3 K选择问题(spine2;extracted/代码精进之路:从码农到工匠(异步图书)/_epub-src/OEBPS/text00001.html;u146-ch09-009)。 - 结论依据:原文在“假设一种理想的情况”附近的定义、实例或代码支撑本卡的核心说明:选择算法只递归目标所在分区。适用边界按该处前提解释,代码未执行。 - 原始内容:假设一种理想的情况,枢轴元素基本位于中间值,即它总是将原数组划分成两个大小基本相等的子数组S (1)和S (2)。 要求解第K 小的元素,有以下3种情况。 (1)若K < |S (1)|,则说明第K 小的元素位于S (1)子数组中。其中,|S (1)| 表示 S (1)