程序员经验分享-hwhale

O(logn) 时间复杂度中 BST 的中位数

2024-01-03

我遇到了给出的解决方案http://discuss.joelonsoftware.com/default.asp?interview.11.780597.8 http://discuss.joelonsoftware.com/default.asp?interview.11.780597.8使用 Morris InOrder 遍历，我们可以找到中位数O(n) time.

但是否可以使用相同的方法来实现O(logn)时间？这里也有人问过同样的问题 -http://www.careercup.com/question?id=192816 http://www.careercup.com/question?id=192816


如果您还维护节点的左右后代数量的计数，则可以通过搜索中间位置来在 O(logN) 时间内完成。事实上，你可以在 O(logn) 时间内找到第 k 大元素。

当然，这是假设树是平衡的。维护计数不会改变插入/删除的复杂性。

如果树不平衡，则最坏情况复杂度为 Omega(n)。

See: 订单统计树 http://pine.cs.yale.edu/pinewiki/OrderStatisticsTree.

顺便说一句，BigO 和 Smallo 非常不同（你的标题说 Smallo）。

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

Algorithm

datastructures

Traversal

treetraversal

O(logn) 时间复杂度中 BST 的中位数 的相关文章

  • 时间复杂度和运行时间有什么区别？

    时间复杂度和运行时间有什么区别 它们是一样的吗 运行时间是指程序运行所需的时间 时间复杂度是对输入大小趋于无穷大时运行时间渐进行为的描述 您可以说运行时间 是 O n 2 或其他什么 因为这是描述复杂性类和大 O 表示法的惯用方式 事实上

  • 如何仅使用单个数组在 JavaScript 中模拟调用堆栈

    我正在看维基百科页面 https en wikipedia org wiki Call stack在调用堆栈上 并尝试理解这个图像 据我所知 哈哈 const memory memory 0 3 top of stack pointer m

  • 生成所有多集大小为 n 的分区的算法

    我一直在试图找出一种方法来生成多重集的所有不同的大小为 n 的分区 但到目前为止却空手而归 首先让我展示一下我想要实现的目标 假设我们有一个输入向量uint32 t std vector

  • 在常数空间中创建 1..N 的随机排列

    我正在寻找枚举固定空间中数字 1 N 的随机排列 这意味着我无法将所有数字存储在列表中 原因是 N 可能非常大 超过可用内存 我仍然希望能够一次遍历这样一个数字的排列 只访问每个数字一次 我知道对于某些 N 可以这样做 许多随机数生成器随机

  • 如何有效地找到距给定点最远的点（从一组点中）？

    我正在寻找一种算法或数据结构来解决以下问题 给你一组点 S 然后你会得到另一个点形式的 Q 查询 对于每个查询 找到集合中距离给定点最远的点 集合中最多有 10 5 个点和 10 5 个查询 所有点的坐标都在 0 到 10 5 范围内 我想

  • 时间序列数据预处理 - numpy strides 技巧以节省内存

    我正在预处理一个时间序列数据集 将其形状从二维 数据点 特征 更改为三维 数据点 时间窗口 特征 在这样的视角中 时间窗口 有时也称为回顾 指示作为输入变量来预测下一个时间段的先前时间步长 数据点的数量 换句话说 时间窗口是机器学习算法在对

  • 迭代任意大小的子集

    我可以迭代大小为 1 的子集 for int a 0 a lt size a 或大小为 2 的子集 for int a1 0 a1 lt size a1 for int a2 a1 1 a2 lt size a2 or 3 for int

  • 生成二叉树的所有从根到叶的分支

    抱歉 如果这是一个常见问题 但我还没有找到适合我的特定问题的答案 我正在尝试实施一个walk方法将二叉树从根节点遍历到每个叶节点 每当到达叶节点时都会生成根到叶路径 例如 遍历表示为的二叉树 a b d c 会产生 a b c a d 我的

  • 如何从迭代器推导连续内存

    不知何故 本土stl copy VC Dinkumware 上的算法表明它可以使用memcpy 可以轻松复制的数据 一个凡人能做到这一点吗 假设每个元素都是普通可复制的 random access iterator 是否意味着连续内存 标准

  • 归并排序中递归树的高度log(n)+1是怎么来的

    我按照 stackoveflow 的建议阅读了一些问题和答案 我正在遵循 cormen 的 算法简介 一书进行自学 那本书里已经解释得很清楚了 但唯一没有解释的是如何在合并排序分析中计算树的高度 如果在后面的章节中对此进行解释的话 我仍然在

  • Florian 的 Grisu2 算法如何工作？

    我遇到了一个关于将 double 转换为 ascii 的问题 经过搜索 我得到了 Florian 的论文 使用整数快速准确地打印浮点数 http www cs tufts edu nr cs257 archive florian loits

  • 在 O(n) 时间内排序？

    我被这个问题困扰了 2周 知道如何处理它吗 令 L 为 n 个不同整数的列表 假设 L 的 x 的元素在 1 750 范围内 设计线性排序算法对 L 的元素进行排序 我已经尝试过插入排序 但我不确定我的方法是否正确 Construct an

  • 在java中使用BUBBLE SORT对二维字符串数组进行排序

    类似的问题已经被问过 但从来没有关于二维字符串数组 因此在尝试了很长时间之后我找不到我想要的 我正在尝试使用 BubbleSort 对 java 中的 2D 字符串数组进行排序 作为输入 我收到一个二维字符串数组 一个表 以及您应该排序的

  • n 或 nlog(n) 比常数时间或对数时间更好吗？

    在 Coursera 上的普林斯顿教程中 讲师解释了遇到的常见增长顺序函数 他说 线性和线性算术运行时间是 我们努力的目标 他的推理是 随着输入大小的增加 运行时间也会增加 我认为这是他犯了错误的地方 因为我之前听过他提到线性增长顺序对于高

  • 有没有时间复杂度为O(N)的排序算法？

    大多数排序算法的复杂度为 O NN 或 O NlogN 来实现结果 但是 对于特定的输入集 有些算法的复杂度为 O N 我想知道是否有一种排序算法在所有情况下都具有 O N 的复杂度 如果您只能比较 检查两个项目是否为 正在排序的值 那么您

  • Linux内核container_of宏和C90中的通用容器

    是否有可能实施容器的 http lxr linux no linux tools perf util include linux kernel h L18纯C90中的宏 我不确定如何做到这一点 因为内核实现取决于海湾合作委员会黑客 http

  • 动态规划 (DP) 中的重叠子问题是什么？

    为了使动态规划适用 问题必须具有两个关键属性 最优子结构 and 重叠子问题 1 https en wikipedia org wiki Dynamic programming 对于这个问题 我们只关注后一个属性 有各种不同的定义重叠子问题

  • 归并排序中的递归：两次递归调用

    private void mergesort int low int high line 1 if low lt high line 2 int middle low high 2 line 3 mergesort low middle l

  • 选择一组数字以达到最小总数的算法

    给定 一组数字n 1 n 2 n 3 n x 还有一个数字M 我想找到最好的组合 n a n b n c n gt M 该组合应达到达到或超过 M 所需的最小值 没有其他组合可以提供更好的结果 将在 PHP 中执行此操作 因此可以使用 PH

  • 生产代码中的 LRU 实现

    我有一些 C 代码 需要使用 LRU 技术实现缓存替换 目前我知道两种实现LRU缓存替换的方法 每次访问缓存数据时使用时间戳 最后比较替换时的时间戳 使用缓存项的堆栈 如果最近访问过它们 则将它们移动到顶部 因此最后底部将包含 LRU 候选

随机推荐

  • 在 HTML5 画布中绘制带有线性渐变的圆弧

    我在画布上画了一个圆弧 是否可以给它提供三种颜色的线性渐变 是的 这是可能的 Javascript中有一个方法 名为createLinearGradient它获取画布上下文作为源并应用由sx sy dx dy坐标 前两个选项定义起始坐标 后

  • 除了 12 小时后会话超时之外，Google Colab 还有其他限制吗？

    限制之一是每次会话只能持续 12 小时 GPU和TPU的使用有限制吗 是的 您只能使用 1 个 GPU 内存有限为 12GB TPU 具有 64 GB 高带宽内存 您可以在此处阅读article https medium com janni

  • 如何测量 NodeJS 中请求花费的时间

    const axios require axios axios get url then response gt console log response catch err gt console log err 我如何测量网站返回整页需要

  • 什么是 ORM，它是如何工作的，以及我应该如何使用它？ [关闭]

    Closed 这个问题需要多问focused help closed questions 目前不接受答案 Locked 这个问题及其答案是locked help locked posts因为这个问题是题外话 但却具有历史意义 目前不接受新的

  • 如何检测试剂中的“Enter”按键？

    给出以下代码 input type text value text app state on change fn e if 31 keyCode e println ENTER println NOT ENTER 如何更改if条件以便可以将

  • 为什么 Swift 不允许非可选类型的弱引用？

    这并不是纯粹的好奇 有一种感觉 我可能误解了 Swift 中弱引用的一些内容 假设我从视图控制器创建一个类并将其引用传递给初始化程序 class MyClass vc self 由于情节提要和窗口已经保留对此视图控制器的引用 因此 MyCl

  • 带德国日期的 Strftime

    我正在尝试用 strftime 打印德语日期 我已经尝试过了 date default timezone set Europe Berlin setlocale LC ALL de DE de DE euro deu deu deu ger

  • 如何从base64解码视频？

    我想在 base64 字符串中转换视频 所以我通过 android 中的视频转换 migBase64 方法 它将视频成功转换为字符串 但是当我将字符串解码为视频时 它无法在视频中正确转换 所以如果有人知道请帮助我 我尝试如下代码 Strin

  • Get-WinEvent 开始和结束日期不过滤记录

    get winevent 开始和结束日期不是过滤记录 谁能告诉我为什么 我期望从最近 2 天事件下面的代码中获得数据 但我得到的日期可以追溯到 2010 年 我的 Windows 时钟日期是正确的 String ComputerName e

  • JS：重命名变量以进行重构（使用 AST，而不是文本）

    我经常需要在重构代码时重命名变量 目前我使用正则表达式以一种有点老套的方式做 我最终不得不使用愚蠢的文本解决方案来解决缺乏实际结构的问题 例如 将 req 重命名为 request 并避免具有类似名称 例如 require 的副作用 想想这

  • Ruby 中 And/&& 的运算符优先级 [重复]

    这个问题在这里已经有答案了 我有一个关于 Ruby 中的 and 关键字的问题 ruby 文档说上述关键字的优先级是 1 2 3 and 我写了这段代码 def f n n end if a f 2 and b f 4 then puts

  • 在 YIi 中建立关系时的条件

    Agent agent id primary key User f id foreign key type 我以这种方式创建了关系 public function relations return array user gt array s

  • AttributeError：“NoneType”对象没有属性“_inbound_nodes”

    我想实施损失函数 https i stack imgur com FI9JH png定义在这里 我使用fcn VGG16获得地图x 并添加激活层 x是fcn vgg16网络的输出 然后只需进行一些操作即可提取特征 co map Activa

  • std::is_function 无法将模板参数识别为函数

    我将函数指针传递到函数模板中 int f int a return a 1 template

  • Git 反转暂存区

    我的暂存区域已发生更改 而其他文件尚未暂存 某些文件在暂存区域内外都有更改 我想反转暂存区域的内容和未暂存的更改 是否存在快捷方式可以做到这一点 而不执行更复杂的操作 例如本地侧分支提交 差异或存储 等 谢谢 我是这样做的 将索引提交到临时

  • 注册接收者的正确模式？

    我需要注册一个接收者 我一直在使用以下模式 Override protected void onResume super onResume registerReceiver myReceiver new IntentFilter Overr

  • pip.conf 中私有 PyPI 的凭据

    我有一个私人 PyPI 存储库 有什么办法可以存储凭据pip conf如同 pypirc 我的意思是 目前在 pypirc你可以有这样的配置 distutils index servers custom custom repository

  • Laravel excel导出如何导出条件数据？

    我正在尝试从表中导出部分数据而不是所有数据 我正在使用 Maatwebsiteplugin https laravel excel com 我在控制器中尝试过以下代码 public function report Request reque

  • 带下划线的字母数字正则表达式模式

    我正在扩展 CodeIgniter 表单验证库来检查带下划线的字母数字值不包括破折号 但我对正则表达式模式非常陌生 需要一些帮助 目前对于 alpha numeric CI 有 return preg match a z0 9 i str

  • O(logn) 时间复杂度中 BST 的中位数

    我遇到了给出的解决方案http discuss joelonsoftware com default asp interview 11 780597 8 http discuss joelonsoftware com default asp

热门标签