程序员经验分享-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) 的相关文章

  • 地图应用的聚类算法

    我正在研究地图上的聚类点 纬度 经度 对于快速且可扩展的合适算法有什么建议吗 更具体地说 我有一系列纬度 经度坐标和一个地图视口 我正在尝试将靠近的点聚集在一起以消除混乱 我已经有了解决问题的方法 see here http bouldr

  • 为什么我的 Project Euler Problem 12 算法这么慢？

    我已经在 Scala 中为 PE P12 创建了解决方案 但速度非常非常慢 有人可以告诉我为什么吗 如何优化这个 calculateDevisors 简单的方法和calculateNumberOfDivisors 除数函数具有相同的速度 i

  • 如何根据递归关系确定递归树的高度？

    如何确定在处理递归运行时时构建的递归树的高度 它与确定普通树的高度有何不同 替代文本 http homepages ius edu rwisman C455 html notes Chapter4 ch4 9 gif http homepa

  • 对给定预定义顺序的字符串列表进行排序

    我有一系列颜色 我想按顺序排序 但是 我不想使用它们的 自然 顺序对它们进行排序 而是让它们保持以下顺序 var order white yellow violet blue orange red maroon brown black 例如

  • 直观地执行不同的排序算法[关闭]

    就目前情况而言 这个问题不太适合我们的问答形式 我们希望答案得到事实 参考资料或专业知识的支持 但这个问题可能会引发辩论 争论 民意调查或扩展讨论 如果您觉得这个问题可以改进并可能重新开放 访问帮助中心 help reopen questi

  • 用于计算三角函数、对数或类似函数的算法。仅限加减法

    我正在修复 Ascota 170 古董机械可编程计算机 它已经开始工作了 现在我正在寻找一种算法来展示其功能 例如计算三角或对数表 或类似的东西 不幸的是 从数学运算来看 计算机只能进行整数的加减法 从 1E12到1E12的55个寄存器 甚

  • 如何设计一种算法来计算倒数式数学数字难题

    我一直想这样做 但每次我开始思考这个问题时 它的指数性质都会让我大吃一惊 我希望能够理解的问题解决器和代码是针对倒计时数学问题的 给定一组数字 X1 到 X5 计算如何使用数学运算将它们组合起来生成 Y 您可以应用乘法 除法 加法和减法 那

  • 如何在单向链表（一次遍历中）中从尾部获取第 n 个节点？

    所以我在一次考试中得到了这个问题 如何从单链表的尾部获取第 n 个节点 每个节点都有一个值和一个下一个 指向下一个值的指针 我们得到这个 getNodeFromTail Node head int x 所以我的做法是通过遍历一次来求出列表的

  • 运行时间为 O(n) 且就地排序的排序算法

    有没有运行时间为O n 并且还分类到位 在某些情况下 最好的情况是 O n 但这可能是因为项目集合已经排序 你正在看 O nlogn 一些较好的平均值 话虽如此 排序算法的 Wiki 还是相当不错的 有一个表格比较了流行的算法 说明了它们的

  • 神经网络的层和神经元

    我想更多地了解神经网络 我正在开发一个 C 程序来制作神经网络 但我坚持使用反向传播算法 很抱歉没有提供一些工作代码 我知道有很多库可以用多种语言创建神经网络 但我更喜欢自己制作一个 关键是我不知道要实现特定目标 例如模式识别或函数近似或其

  • 查找文本中所有关键字的有效算法

    我有很多字符串 其中包含许多不同拼写的文本 我通过搜索关键字来标记这些字符串 如果找到关键字 我将使用该关键字的关联文本 假设搜索字符串可以包含文本 schw schwa 和 施瓦茨 我有三个关键字 全部解析为文本 schwarz 现在我正

  • C++并行std::sort用于浮点值

    我有一个包含数百万个浮点值的大文件 我可以使用轻松对它们进行排序std sort通过将文件读入vector现在 例如 std vector

  • javascript中的父子关系排序

    我有以下结构 category id 1 parent category null category id 2 parent category 1 category id 3 parent category 1 category id 4

  • 检查有效的 IMEI

    有人知道如何检查有效的 IMEI 吗 我找到了一个可以检查此页面的功能 http www dotnetfunda com articles article597 imeivalidator in vbnet aspx http www do

  • Python Pandas：沿一列比较两个数据帧，并返回另一个数据帧中两个数据帧的行内容

    我正在处理两个 csv 文件并作为数据框 df1 和 df2 导入 df1 有 50000 行 df2 有 150000 行 我想将 df2 的 时间 与 df1 求时间差并返回所有列的值 对应相似的行 保存在df3中 时间同步 例如 35

  • 数独算法，暴力破解[关闭]

    这个问题不太可能对任何未来的访客有帮助 它只与一个较小的地理区域 一个特定的时间点或一个非常狭窄的情况相关 通常不适用于全世界的互联网受众 为了帮助使这个问题更广泛地适用 访问帮助中心 help reopen questions 我正在尝试

  • 字符串插值搜索

    对于那些不熟悉插值搜索的人来说 这是一种在排序数组中搜索值的方法 可能比二分搜索更快 您查看第一个和最后一个元素 并 假设数组的内容均匀分布 线性插值以预测位置 例如 我们有一个长度为 100 的数组 其中 array 0 0 和 arra

  • 如何为多边形创建内部螺旋？

    对于任何形状 我如何在其内部创建类似形状的螺旋 这与边界 使用 Minkowski 和 类似 尽管它会是相同形状的螺旋 而不是在形状内部创建相同的形状 我找到了这个 http www cis upenn edu cis110 13su le

  • 如何将多边形放入另一个多边形内[关闭]

    Closed 这个问题需要多问focused help closed questions 目前不接受答案 我有两个多边形 如下图所示 左边是 粗多边形 右边是 最终多边形 现在 我正在寻找算法来将 最终多边形 拟合到 粗糙多边形 内 并具有

  • 如何在 C# 中以编程方式创建柔和的颜色？

    根据所需的颜色数量均匀分布地生成它们 如果指定的计数为 8 则看起来像这样 List

随机推荐

热门标签