程序员经验分享-hwhale

向已包含 n 个元素的二叉堆插入 n 个元素的渐近时间复杂度

2023-11-23

假设我们有一个包含 n 个元素的二叉堆，并且希望再插入 n 个元素（不一定是一个接一个）。总共需要多少时间？

我认为它是 theta (n logn)，因为一次插入需要 logn。


给定：n 个元素的堆以及要插入的 n 个元素。所以最终会有2*n个元素。因为堆可以通过两种方式创建：1.连续插入和2.构建堆方法。在这些构建堆方法中，构建堆需要 O(n) 时间，这在构建堆的时间复杂度怎么可能是O(n)？。所以所需的总时间是 O(2*n) ，与 O(n) 相同

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

Algorithm

datastructures

asymptoticcomplexity

binaryheap

向已包含 n 个元素的二叉堆插入 n 个元素的渐近时间复杂度 的相关文章

  • 整数除法性质

    下面的整数算术性质成立吗 m n l m n l 起初我以为我知道答案 不成立 但现在不确定 它适用于所有数字还是仅适用于某些条件 即n gt l 该问题涉及计算机算术 即q n m q m n 忽略溢出 Case1 assume m kn

  • 比较两棵树的伪代码

    这是我遇到过几次的问题 并且不确信我使用了最有效的逻辑 例如 假设我有两棵树 一棵是文件夹结构 另一棵是该文件夹结构的内存 模型 我希望比较两棵树 并生成一棵树中存在的节点列表 而不是另一棵树中存在的节点列表 反之亦然 是否有公认的算法来处

  • 对列表中的相邻元素进行分组

    假设我想编写一个函数来执行此操作 输入 1 1 3 3 4 2 2 5 6 6 输出 1 1 3 3 4 2 2 5 6 6 它将相同的相邻元素分组 这个方法的名称应该是什么 此操作有标准名称吗 In 1 1 3 3 4 2 2 5 6 6

  • 使用 stl sort 对表进行排序

    我有一个巨大的表 约 50Gb 格式为 i j k 来自稀疏矩阵 存储为 uint32 t idx1 idx2 float vals uint32 t tablesize 我想使用给定的比较函数 即 idx1 和 idx2 的函数 对其进行

  • 如何将多个值存储到一个键（java）

    我搜索一个可以存储多个键值对的数据结构 数据基本上是这样的 1 value 1 2 value 2 于是我想到了使用HashMap 遗憾的是 这对我不起作用 因为一个键可能会出现多个值 在上面的例子中 1 value 2 可能是另一个条目

  • 如何使用networkx删除有向图中的所有相关节点？

    我不确定我的问题的正确术语是什么 所以我只会解释我想做的事情 我有一个有向图 删除节点后我希望所有独立相关的节点也被删除 这是一个例子 假设我删除节点 11 我希望节点 2 也被删除 在我自己的示例中 它们将是 2 以下的节点 现在也必须删

  • java中的Anagram算法

    我想做字谜算法但是 这段代码不起作用 我的错在哪里 例如 des 和 sed 是字谜 但输出不是字谜 同时我必须使用字符串方法 不是数组 public static boolean isAnagram String s1 String s2

  • 查找两个大小为 n 的数组中第 n 大数的算法

    我有这个问题 给定两个大小为 n 的排序列表 存储在数组中 找到 O log n 计算并集中第 n 大元素的算法 两个列表 我可以看到这里可能有一个技巧 因为它需要第 n 个最大的元素 并且数组的大小也是 n 但我不知道它是什么 我在想我可

  • 算法 - 树中所有节点的最大距离

    所以 找到树中两个节点之间的最长路径相当容易 但我想要的是找到从节点出发的最长路径x到树中的另一个节点 对于所有x 这个问题也可以用以下方式表达 计算从给定的树中可以生成的所有有根树的高度 One way of course is to j

  • 为什么使用 no-op 来填补 paxos 事件之间的空白是合法的？

    我正在学习Paxos算法 http research microsoft com en us um people lamport pubs paxos simple pdf http research microsoft com en us

  • n的渐近增长选择下限(n/2)

    如何找到 n select Floor n 2 的渐近增长 我试过 使用扩展并得到它等于 n n 1 floor n 2 1 n floor n 2 知道我该如何从那里去吗 感谢任何帮助 更喜欢提示而不是答案 我同意上面的答案 但想提供更多

  • 如何在大空间尺度上加速A*算法？

    From http ccl northwestern edu netlogo models community Astardemo http ccl northwestern edu netlogo models community Ast

  • 大小为 n 的数组，其中一个元素 n/2 次

    给定一个由 n 个整数组成的数组 其中一个元素出现超过 n 2 次 我们需要在线性时间和恒定的额外空间中找到该元素 YAAQ 又一个数组问题 我有一种偷偷的怀疑 这类似于 在 C 中 We don t need an array publi

  • 模式识别算法

    过去我必须开发一个充当规则评估器的程序 你有一个先行词和一些后续词 动作 所以如果先行词评估为真 则执行的动作 当时我用的是修改版RETE算法 http en wikipedia org wiki Rete algorithm RETE 有

  • 为什么 n 按位和 -n 总是返回最右边的位（最后一位）

    这是Python代码片段 1 1 1 2 2 2 3 3 1 看来任何n n总是返回最右边 最后 位 我真的不知道为什么 有人可以帮助我理解这一点吗 这是由于负数以二进制表示的方式 称为二进制补码表示 创建某个数字 n 的补码 换句话说 创

  • javascript - 找到在一定限制下给出最大总和的子集（子集总和）

    我有一个包含一些整数值的数组 我需要获取它们的子集 该子集给出小于给定值的最大总和 假设我有这个数组 40 138 29 450 我想获得该数组的一个子集 使总和最大化 但低于用户给出的限制 比如说 250 在这种情况下 它应该返回 139

  • 我该如何解决？ KnapSack - 值完全相同，但每个对象都有三个权重

    我在解决我的练习时遇到问题 我读到了动态规划和算法 我认为我的练习是 特定背包问题 我用暴力法解决了它 但我无法用动态规划解决它 我有一艘重300吨的船 背包 有些晶体本身含有 3 种物质 X Y Z 每种物质都有重量 并且所有晶体都具有相

  • 单词预测算法

    我确信有一篇关于此问题的帖子 但我找不到提出这个确切问题的帖子 考虑以下 我们有字典可供使用 我们收到了许多单词段落 我希望能够根据此输入预测句子中的下一个单词 假设我们有几个句子 例如 你好 我的名字是汤姆 他的名字是杰瑞 他去了没有水的

  • 使用向量的 merge_sort 在少于 9 个输入的情况下效果很好

    不知何故 我使用向量实现了合并排序 问题是 它可以在少于 9 个输入的情况下正常工作 但在有 9 个或更多输入的情况下 它会执行一些我不明白的操作 如下所示 Input 5 4 3 2 1 6 5 4 3 2 1 9 8 7 6 5 4 3

  • Java中获取集合的幂集

    的幂集为 1 2 3 is 2 3 2 3 1 2 1 3 1 2 3 1 假设我有一个Set在爪哇中 Set

随机推荐

  • 应用程序配置错误 抱歉，myapp 尚未获准在应用程序中心显示。在 Android 应用程序中共享

    当我在 Facebook 上点击我的应用程序名称时 它重定向到 https www facebook com games app id 827708240586758 并显示 应用程序配置错误抱歉 我的应用程序尚未获准在应用程序中心显示 我

  • 如何在不使用故事板的情况下创建 UICollectionView？

    我在网上找到了一些不错的 UIcollectionview 教程 http www raywenderlich com 22324 beginning uicollectionview in ios 6 part 12 http ashfu

  • AppBarLayout 以编程方式更改偏移量

    如何以编程方式更改 AppBarLayout 的偏移量 当 Activity 首次加载时 我希望 AppBarLayout 部分展开 有一定的偏移量 然后用户可以进一步展开它或折叠它 当前的行为是当 Activity 首次加载时它完全展开

  • 交换 gnuplot 中的轴

    我想知道这个有一段时间了 它可能已经在gnuplot但我一直无法在网上找到信息 当您有数据文件时 可以交换轴并将 虚拟变量 例如 x 在 gnuplot 的帮助术语中 分配给垂直轴 plot data u 1 2 x goes to hor

  • 使用事务进行rails数据库迁移

    我刚刚学习 Rails 并开始了有关数据库迁移的部分 我构建了 2 个迁移 并且都成功迁移了 向下迁移 最新的迁移 即第一个运行的迁移 由于我的代码中的拼写错误而失败 我修复了拼写错误 但此后迁移仍然失败 我发现原因是向下迁移在更改中途中止

  • Laravel 5.6 中的 url() 与 Route()

    就我而言 Laravel 5 6 中的 url 和 route 有什么区别 下面给出了两个 URI a href Create post 1 a and a href Create post 2 a 我在 web php 中定义它们如下 R

  • 为什么需要 useRef 而不是可变变量？

    我读过了useEffect 完整指南 逆流而上反应过度 该示例表明 如果我们想获取最新的count 我们可以用useRef保存可变变量 并在异步函数中获取它 function Example const count setCount use

  • Android 在回收站视图中水平自动滚动

    我在列表中有两个值 并使用回收器视图在水平列表视图中显示它们 这里我需要无限地自动滚动水平列表 我尝试使用下面的代码但没有结果 Horizo ntalScrollView 添加新视图时自动滚动到结束 请在此处查看解决方案 https git

  • 您可以在 List 中的位置 0 处插入吗？

    我需要在集合的开头插入一个对象 我的收藏是列表类型 我怎样才能做到这一点 当然可以 例如一个通用的字符串列表 List

  • 如何让 Visual Studios 构建系统了解托管 dll 的非托管依赖关系？

    构建托管代码时 Visual Studio 正确 并递归地 将引用的托管项目的 dll 复制到正在构建的项目的输出文件夹中 但是 如果这些引用之一是依赖于非托管 DLL 的托管 DLL 则这些非托管 DLL 不会复制到输出文件夹 即使它们的

  • :after 伪元素的 CSS3 转换

    看看这个小提琴 http jsfiddle net sajYc 过渡为 after伪元素在 Firefox 中工作 但在基于 webkit 的浏览器中失败 知道这是否会在未来的版本中出现吗 有什么非 jquery 过度杀伤的解决方法吗 基本

  • 为什么 :before 在 safari 中看不到？

    我有一个在 Chrome 中运行良好的代码 menu ul list style position inside list style type none display block margin 0 auto padding 0 menu

  • 在单独的 .swift 文件中使用扩展名

    寻找在单独的文件中使用 Swift 扩展的方法或替代解决方案 仅当扩展被写入正在使用的同一文件中时 创建扩展才有效 这是一个有效的 ViewController swift 示例 import UIKit var TestHelper St

  • C++ 将向量转换为向量

    什么是一个好的干净的方法来转换std vector

  • 扁平化 TypeScript 类型或界面？

    作为一名 TypeScript 开发人员 我已经习惯了在使用时出现 重复标识符 问题 d ts files 最近 发生这种情况是因为我需要两种打字 d ts文件 Angular 2 和 Parse Angular 2 不分发它们的 d ts

  • WordPress：如何将 url GET 参数添加到我的主菜单项

    我正在尝试将 URL GET 参数添加到 Wordpress 中的主菜单项之一 但我不知道如何操作 因此 我的方法是检测菜单项上的单击事件 然后通过 AJAX 将参数传递到我的 php 页面 该页面将处理根据需要传递的值 我的主要问题是 看

  • 完整克隆是子模块添加分支的唯一方法吗？

    我想添加一个引用特定 非主 分支的子模块 以下只会抓取 master 分支 因为 depth 1 所以命令必然会失败 git submodule add b myBranch depth 1 email protected some lar

  • 如何使用 AngularJS 并调用 MVC API 下载文件？

    我正在使用 AngularJS 并且有一个 MVC 4 API 它返回带有附件的 HttpResponseMessage var result new MemoryStream pdfStream 0 pdfStream Length Po

  • Numpy 温度计编码

    我正在尝试使用 numpy 优化的内置函数来生成温度计编码 温度计编码基本上是生成n如果 1 在给定长度内 则为数量 例如 在 8 长度中 3 将被编码为 1 1 1 0 0 0 0 0 使用 numpy 根据整数输入生成该向量基本上是切片

  • 向已包含 n 个元素的二叉堆插入 n 个元素的渐近时间复杂度

    假设我们有一个包含 n 个元素的二叉堆 并且希望再插入 n 个元素 不一定是一个接一个 总共需要多少时间 我认为它是 theta n logn 因为一次插入需要 logn 给定 n 个元素的堆以及要插入的 n 个元素 所以最终会有2 n个元

热门标签