程序员经验分享-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 个元素的渐近时间复杂度 的相关文章

  • 给定与总和匹配的长度的唯一 3 位数字 (-1,0,1) 序列的数量

    假设您有一个长度为 n 即空格数 的垂直游戏板 你有一个三面骰子 有以下选项 前进一 停留和后退 如果您低于或高于棋盘游戏空间的数量 则该游戏无效 一旦到达棋盘末端 唯一有效的动作就是 停留 给定确切的骰子投掷次数 t 是否可以通过算法计算

  • 根据多个值过滤字典列表

    我有一个字典列表 我想根据多个条件进行过滤 该列表的简化版本如下所示 orders name v price 123 location Mars name x price 223 location Mars name x price 124

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

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

  • 两个非嵌套循环的大 O 表示法

    对于两个非嵌套的 for 循环 大 O 表示法是什么 Example for int i 0 i

  • 反转二进制网络

    如何反转二元方程 以便找到哪些输入将产生给定的输出 Example Inputs i0 through i8 Outputs o0 through o8 Operators XOR AND 二元方程 1 i0 1 i1 0 i2 1 i3

  • 初始化 HashMap 的最佳方法

    我通常会这样做 HashMap

  • Java：如何实现3和？

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

  • 搜索/排序算法 - 是否有类似 GoF 的列表？

    我是一名自学成才的开发人员 坦率地说 我不太擅长找出在任何特定情况下使用哪种搜索或排序算法 我只是想知道是否有设计模式 esque 列出了以太坊中可用的常见算法 供我添加书签 就像是 算法名称 带有别名 如果有的话 它解决的问题 大O成本

  • 为什么在排序输入上插入到树中比随机输入更快？

    现在我一直听说从随机选择的数据构建二叉搜索树比有序数据更快 这仅仅是因为有序数据需要显式重新平衡以将树高度保持在最低限度 最近我实现了一个不可变的treap http en wikipedia org wiki Treap 一种特殊的二叉搜

  • 用 Java 创建迷宫求解算法

    我被分配了用 Java 创建迷宫求解器的任务 这是任务 Write an application that finds a path through a maze The maze should be read from a file A

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

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

  • 从日志文件中获取前 100 个 URL

    我的一位朋友在接受采访时被问到以下问题 谁能告诉我如何解决它 我们有一个相当大的日志文件 大约 5GB 日志文件的每一行都包含一个用户在我们网站上访问过的 URL 我们想要找出用户访问最多的 100 个 URL 怎么做 如果我们有超过 10

  • 编程 Pearls - 随机选择算法

    Programming Pearls 第一版第 120 页介绍了从 N 个整数总体中选择 M 个等概率随机元素的算法 InitToEmpty Size 0 While Size lt M do T RandInt 1 N if not Me

  • 将嵌套字典中的所有键从camelCase转换为snake_case

    我有一本类似这样的字典 firstName abc lastName xyz favoriteMovies Star Wars The lone ranger favoriteCountries country China capitalC

  • 快速求解子集和

    考虑这种解决子集和问题的方法 def subset summing to zero activities subsets 0 for activity cost in activities iteritems old subsets sub

  • java数据结构模拟数据树

    我需要帮助定义使用什么方法 我有一个 SOAP 响应 给我一个 xml 文件 我需要在屏幕上显示 3 个相关列表 当您在第一个列表中选择一个项目时 相应的选择将出现在第二个列表中 依此类推 我只对从 xml 流中提取数据后如何有效地组织数据

  • 高维最近邻搜索的最佳数据结构

    我实际上正在处理高维数据 50 000 100 000 个特征 并且必须对其执行最近邻搜索 我知道随着维度的增长 KD 树的性能很差 而且我还了解到 一般来说 所有空间分区数据结构都倾向于对高维数据执行详尽的搜索 此外 还有两个重要事实需要

  • 图中的后边

    I m having a hard time understanding Tarjan s algorithm for articulation points I m currently following this tutorial he

  • 快速搜索压缩文本文件

    我需要能够在大量压缩文件 txt 中搜索文本 压缩可能会改变为其他东西 甚至成为专有的 我想避免解压所有文件并压缩 编码 搜索字符串并在压缩文件中搜索 这应该可以通过对所有文件使用相同的码本使用霍夫曼压缩来实现 我不想重新发明轮子 所以 任

  • 找到一系列间隔的最有效分组

    我有一个应用程序 其中有一系列不重叠的固定宽度间隔 每个间隔都有一个给定的键 每个间隔具有相同的宽度 并且可以存在连续的间隔 本质上 我想以最小化单独间隔的数量的方式对间隔和键进行分组 这可以通过合并具有相同键的连续间隔或查找匹配间隔并将它

随机推荐

  • 应用程序配置错误 抱歉，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个元

热门标签