程序员经验分享-hwhale

稳定的比较排序，时间复杂度为 O(n * log(n))，空间复杂度为 O(1)

2024-03-19

在经历的同时维基百科的排序算法列表 https://secure.wikimedia.org/wikipedia/en/wiki/Sorting_algorithm#Comparison_of_algorithms我注意到没有稳定的比较排序 https://secure.wikimedia.org/wikipedia/en/wiki/Comparison_sort具有O(n*log(n))（最坏情况）时间复杂度和O(1)（最坏情况）空间复杂度。这看起来确实像是一个理论边界，但我找不到更多关于它的信息。

如何证明这一点呢？

注意：我知道的下限O(n*log(n))比较排序的最坏情况时间复杂度。


不管那篇文章怎么说，可以进行就地稳定的归并排序O(n log n) https://secure.wikimedia.org/wikipedia/en/wiki/Merge_sort#Analysis.

是一篇解释了实现它的两种方法的论文。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm

Sorting

complexitytheory

proof

稳定的比较排序，时间复杂度为 O(n * log(n))，空间复杂度为 O(1) 的相关文章

  • Google Sheets - 如何将过滤功能与过滤视图结合起来

    我一直在处理一个包含 100 多行的电子表格 并发现了一种巧妙的方法来合并 隐藏 复选框 该复选框将隐藏 C 列与框旁边指定的特定值 建筑类型 匹配的任何行 为此 我首先创建了一个如下函数 FILTER Data A1 OR Data C1

  • 如何最小化两个子多边形的最大纵横比？

    我想使用直线将凸多边形切成给定面积比的两部分 以使两个子多边形的较大纵横比最小化 目前我的方法包括选择一个随机起点 计算将多边形分割成目标区域的适当终点 然后计算两个纵横比中较大的一个 然后重复这个很多次 直到我足够接近最小值 多边形 A

  • 获取无平方数的列表

    获得该值的一种方法是自然数 1 n 我们对每个因子进行因式分解 看看它们是否有重复的质因数 但这对于大的情况来说会花费很多时间n 那么有没有更好的方法从 1 中获取无平方数n 您可以使用埃拉托斯特尼筛法的修改版本 取一个布尔数组 1 n 预

  • Java：使用indexOf方法根据另一个数组对数组进行排序

    我想根据另一个数组 索引 的排序顺序迭代两个数组 A B 在本例中为 10 34 32 21 String A a b c d String B e f g h int indexes 10 34 32 21 为这里的坏例子道歉 我已经更新

  • 给定两个（大）点集，我如何有效地找到彼此最接近的点对？

    我需要解决一个计算问题 该问题归结为搜索两个集合之间最接近的点对 问题是这样的 给定欧几里德空间中的一组点 A 和一组点 B 找到所有对 a b 使得 b 是 B 中与 a 最近的点 a 是 A 中与 b 最近的点 集合 A 和 B 的大小

  • 4 x 3 锁图案

    我遇到了这个 它要求计算在 4x3 网格中可以制作特定长度的锁定图案的方式数 并遵循规则 可能有些点不能包含在路径中 有效的模式具有以下属性 图案可以使用第一次接触的点序列来表示 与绘制图案的顺序相同 从 1 1 到 2 2 的图案与图案不

  • 如何使用KDTrees实现最近邻搜索？

    所以 我正在实施一个KD Tree http en wikipedia org wiki Kd tree进行最近邻搜索 我已经构建了树部分 但我认为我没有完全理解搜索部分 关于遍历树来搜索邻居 维基百科文章如下 Starting with

  • 用于插入/删除/排名/选择查询的最佳数据结构/算法

    到目前为止 我知道像AVL树和红黑树这样的自平衡BST可以在O log n 次内完成这些操作 然而 要使用这些结构 我们必须自己实现AVL树或RB树 我听说有一个算法 实现这四个操作而不使用自平衡 BST 有了我们自己定义的结构 我们就需要

  • 稀疏矩阵中的最大和子矩形

    求一个子矩形中的最大和NxN矩阵可以完成O n 3 正如其他帖子中指出的 使用 2 d kadane 算法的时间 然而 如果矩阵是稀疏的 具体来说O n 非零条目 可以O n 3 时间被打败了吗 如果有帮助的话 对于我感兴趣的当前应用程序

  • 加密成本高，解密成本低

    我希望该用户 攻击者加密数据并发送给服务器 现在我想要一种与标准算法完全相反的算法 使用快 难以解密 即很难使用服务器发送的密钥来加密密码等数据 以防止随机攻击 但很容易解密这样服务器在验证用户时消耗的时间非常少 但是对于攻击者来说 每次使

  • 如何在 PHP 中对数组和数据进行排序？

    这个问题旨在作为有关 PHP 中数组排序问题的参考 人们很容易认为您的特定案例是独特的并且值得提出新问题 但大多数实际上只是此页面上的解决方案之一的微小变化 如果您的问题因与此问题重复而被关闭 请仅在您能解释为什么它与以下所有问题显着不同的

  • C中的链表按升序排序

    我正在为我的 C 编程课程编写一个程序 该程序应该为我们提供使用链表的经验 作业的最后部分之一要求我们获取一个链接列表 并使用我们之前在程序中编写的前置或附加函数按升序对其进行排序 struct lnode int datum struct

  • 对模板之一的 observableArray 进行排序

    我有以下视图模型 function instance id FirstName extend this id ko observable id FirstName ko observable FirstName 我在 observableA

  • Java：如何实现3和？

    我正在研究 3 Sum 来自己实现它 并遇到了以下规则的实现 给定一个由 n 个整数组成的数组 S S 中是否存在满足 a b c 0 的元素 a b c 查找数组中所有总和为零的唯一三元组 注意 三元组 a b c 中的元素必须按非降序排

  • 使用快速排序查找数组中第 k 个最小的项 => 预期运行时间？

    如果我使用快速排序的修改版本来查找数组中第 k 个最小的项目 为什么预期运行时间是 O n 如 Programming Pearls 一书中所述 我正在使用的算法执行以下操作 1 Runs quick sort on the array 2

  • 如何从二叉搜索树中均匀随机地返回节点？

    给定一个 BST 可能平衡也可能不平衡 如何能够均匀地随机返回 任何 节点 一个限制是您不能使用外部索引数据结构 您必须以每个节点都有平等被访问的机会的方式遍历树 这个问题让我困惑了好一阵子 如果我们确实可以使用外部哈希表 指针 我们可以对

  • 对 Objective-c 对象数组进行排序

    所以我有一个自定义课程Foo有许多成员 interface Foo NSObject NSString title BOOL taken NSDate dateCreated 在另一堂课上我有一个NSMutableArray包含这些对象的列

  • cordova 使用什么 js“引擎”？

    Cordova 使用什么 JS 引擎 它是特定于平台的还是跨所有平台的一个标准 意味着 iOS 的 safari 和 Android 的 chrome 以及 Windows 可能的 IE 标准 或者跨所有平台的 Cordova JS 引擎

  • 32 位数字中 1 的数量

    我正在寻找一种在 32 位数字中包含 1 数量的方法 之间不使用循环 任何人都可以帮助我并向我提供代码或算法吗 这样做 提前致谢 See Integer bitCount int http java sun com javase 6 doc

  • 字符串排序真的是 O(n^2logn) 吗？ [复制]

    这个问题在这里已经有答案了 我读了以下内容 排序需要 O NlogN 那么它怎么是 O N 2logN 我们在这里想念的是 两个字符串的比较不是 O 1 在最坏的情况下 需要 在 所以最终的复杂度是O N 2logN 它是否正确 我一直认为

随机推荐

热门标签