程序员经验分享-hwhale

简单不平衡搜索树的平均渐近深度是多少？

2023-12-19

对于平衡搜索树，所有情况都是 O(log(N))。对于不平衡搜索树，最坏情况是 O(N)，例如插入 1, 2, 3, 4,..，最好情况复杂度是平衡时，例如插入 6, 4, 8, 3, 5 7 . 我们如何定义不平衡搜索树的平均情况复杂度？


二叉树的平均高度为 Theta(sqrt(n))。这已在以下论文中显示（或引用，不太确定）：http://www.dtc.umn.edu/~odlyzko/doc/arch/extreme.heights.pdf http://www.dtc.umn.edu/~odlyzko/doc/arch/extreme.heights.pdf.

但也许您对随机节点的平均深度更感兴趣，这是 Theta(log n)，如下所示：http://www.toves.org/books/data/ch05-trees/index.html http://www.toves.org/books/data/ch05-trees/index.html（第 5.2.4 节）。

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

Math

binarytree

Depth

简单不平衡搜索树的平均渐近深度是多少？ 的相关文章

  • 单位安全平方根

    我只是想知道如何以与 F 正确交互的方式编写用户定义的平方根函数 sqrt 单位制 http blogs msdn com andrewkennedy archive 2008 09 04 units of measure in f par

  • 有 JavaScript 的微积分库吗？ [关闭]

    Closed 此问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 有人知道 JavaScript 的微积分库吗 我做了一些谷歌搜索 但没有想出任何东西 我申请了 Wolf

  • 这个方法比 Math.random() 更快吗？

    我是一名初学者 目前已经开始开发一款使用粒子群优化算法的 Android 游戏 我现在正在尝试稍微优化我的代码 并且 for 循环中有相当多的 Math random 几乎一直在运行 所以我正在考虑一种方法来绕过并跳过所有 Math ran

  • 如何在 C 中将 uint 转换为 int，同时将结果范围的损失最小化

    我想要两个无界整数之间的差 每个整数由一个表示uint32 tvalue 是对 2 32 取模的无界整数 例如 TCP 序列号 请注意 模 2 32表示形式可以环绕 0 这与更受限制的问题 不允许环绕 0 https stackoverfl

  • CGPoint 标量乘法 Swift

    我正在 SpriteKit 中构建一个平台游戏 并将为我的实体实现更新功能 以便它们根据重力和速度移动 但是 我需要使添加的速度量与增量时间成比例 以防止帧速率影响我的实体的移动方式 因此我将导入 GLKit 以便我可以使用标量函数 但是

  • 如何舍入、取整、取整、截断

    如何对 jq jq 1 5 1 a5b5cbe 中的数字进行舍入 取整 取整和截断 例如 与 mass 188 72 我想 mass 188 有地板 mass 189 与天花板和圆形 舍入示例 5 52 gt 6 5 50 gt 5 or

  • 在 Matlab 中保存 Kinect 深度图像？

    通过使用 Kinect 我可以获得深度图像 其中每个深度图像像素存储相机和物体之间的距离 以毫米为单位 现在我想保存它们以便以后使用 最好的推荐是什么 我正在考虑将深度图像保存为图像 jpg png等 然而 该值通常是从50毫米到10000

  • 如何确保整数除法始终向上舍入？

    我想确保如有必要 整数除法总是向上舍入 还有比这更好的方法吗 目前正在进行大量选角工作 int Math Ceiling double myInt1 myInt2 更新 这个问题是我2013年1月博客的主题 http ericlippert

  • C++ Exp 与 Log：哪个更快？

    我有一个 C 应用程序 需要比较两个值并决定哪个值更大 唯一的复杂之处是一个数字在对数空间中表示 而另一个则不是 例如 double log num 1 log 1 23 double num 2 1 24 如果我想比较num 1 and

  • 将名称字符串编码为唯一的数字

    我有一大堆名字 数以百万计 他们每个人都有一个名字 一个可选的中间名和一个姓氏 我需要将这些名称编码为唯一代表这些名称的数字 编码应该是一对一的 即一个名称只能与一个数字相关联 一个数字只能与一个名称相关联 对此进行编码的明智方法是什么 我

  • 列出所有 k 元组，其条目总和为 n，忽略旋转

    有没有一种有效的算法来查找所有序列k总和为的非负整数n 同时避免旋转 如果可能的话 完全避免 顺序很重要 但对于我正在解决的问题来说 轮换是多余的 例如 与k 3 和n 3 我想要得到一个如下所示的列表 3 0 0 2 1 0 2 0 1

  • 如果数字小于 10，则显示前导零 [重复]

    这个问题在这里已经有答案了 可能的重复 JavaScript 相当于 printf string format https stackoverflow com questions 610406 javascript equivalent t

  • 应用对数来导航树

    我曾经知道一种使用对数从树的一片叶子移动到树的下一个 有序 叶子的方法 我认为它涉及获取 当前 叶子的位置值 排名 并将其用作从根向下到新目标叶子的新遍历的种子 一直使用对数函数测试来确定是否沿着右或左节点向下到达叶子 我已经不记得如何运用

  • 是什么导致 Java（冰雹序列）在我的程序中崩溃

    我制作了一个执行 通常称为 冰雹序列的程序 该程序基本上执行以下操作 创建一个int 值 并为其分配一个值 如果 int 是偶数 则将其除以二 如果 int 为奇数 则将其乘以三并加一 继续这个过程 直到 n 等于 1 它似乎适用于大多数数

  • O(n^2) 与 O (n(logn)^2)

    时间复杂度是O n 2 or O n logn 2 better 我知道当我们简化它时 它就变成了 O n vs O logn 2 and logn lt n 但是关于logn 2 n is only less than log n 2 f

  • C/C++：指针算术

    我在读一点 指针算术 发现有两件事我无法理解 也不知道它的用途 address expression address expression and also address expression gt address expression

  • 计算机如何评估巨大的数字？

    例如 如果我输入一个值 1234567 98787878 Wolfram Alpha 可以为我提供许多细节 这包括小数近似 总长度 最后一位数字等等 您如何评估如此大的数字 据我了解 编程语言必须具有特殊的数据类型才能存储数字 更不用说将其

  • RNG 技术的可移植性和可重复性

    我可以使用两种方法之一来创建一个伪随机数序列 该序列具有两个重要特征 1 它可以在不同的机器上重现 2 该序列永远不会重复范围内的数字 直到所有数字都被发出 我的问题是 这两种方法在可移植性 操作系统 Python 版本等 方面是否存在潜在

  • 具有最小刻度的图表的漂亮标签算法

    我需要手动计算图表的刻度标签和刻度范围 我知道漂亮刻度的 标准 算法 参见 我也知道这个Java实现 http erison blogspot nl 2011 07 algorithm for optimal scaling on char

  • Python OverflowError：数学范围错误[重复]

    这个问题在这里已经有答案了 当我尝试这个计算时 出现溢出错误 output math exp 1391 12694245 100 我知道发生这种情况是因为使用的数字 超出了双精度数的范围 但有什么方法可以解决这个问题并获得输出值 有人可以帮

随机推荐

  • 如何使用node.js进行AOP？

    我在使用 Node js 进行 AOP 时遇到了一些问题 假设我有一个名为的脚本中的应用程序服务器 js 我想监控它的功能 这是代码 var express require express var app express app get f

  • 合并两个分支，如何接受一个分支来解决所有冲突

    我将两个分支合并在一起 比方说brachA 和branchB 他们有大约 100 个存在冲突的文件 Branch 的所有工作都得到了认可 并且 100 是我所需要的 我不想强制推送分支或任何东西 有没有一种方法可以合并这两个文件 并只说对于

  • 如何在git中列出当前项目的所有日志？

    我使用git log 但我发现它只能列出当前分支下的日志 但我想列出所有分支的所有日志并按修改日期排序 这可能吗 如何做到这一点 提前致谢 你可以检查这个问题 https stackoverflow com questions 220894

  • spring-boot：编译致命错误：目标版本无效：17

    刚刚经历弹簧启动教程 https docs spring io spring boot docs current SNAPSHOT reference htmlsingle getting started first application

  • 在 Visual Studio 中哪里可以观察全局数据结构、变量？

    当我调试并到达断点时 我只能在 Visual Studio 2008 的 局部变量 选项卡中看到局部变量 在 Visual Studio 中哪里可以观察全局数据结构 变量 In the Watch窗户 这Local选项卡用于局部变量 顾名思

  • 使用 ImageMagick 或 Ghostscript（或其他）缩放 PDF 以适合页面？

    我需要缩小一些大型 PDF 以在 8 5x11 英寸 标准信函 页面上打印 ImageMagick Ghostscript 可以处理这类事情吗 还是因为我使用了错误的工具来完成这项工作 所以遇到了很多麻烦 仅仅依靠客户端打印对话框中的 缩小

  • SceneKit：无论您触摸屏幕的何处，unprojectPoint都会返回相同/相似的点

    下面的代码应该将触摸坐标转换为 SceneKit 场景的世界坐标 但是 如下面的输出所示 返回的点unprojectPoint无论您触摸屏幕的哪个位置 iPhone 5s 都会有效地返回同一点 类文档为unprojectPoint建议使用

  • 是否可以仅使用 GPU 来加厚二次贝塞尔曲线？

    我在 OpenGL 程序中绘制了大量二次贝塞尔曲线 现在 曲线只有一像素细 并且是由软件生成的 因为我还处于相当早期的阶段 看看什么有效就足够了 Simply enough given 3 control points P0 to P2 I

  • Django：进行原始 SQL 查询，传递多个/重复参数？

    希望这应该是一个相当简单的问题 我只是对 Python 和 Django 了解不够 无法回答它 我在 Django 中有一个原始 SQL 查询 它采用六个不同的参数 其中前两个 centreLat 和 centerLng 均重复 query

  • C# - 我应该如何将 datagridview 组合框添加到数据表并在 datagridview 中预览它？

    抱歉 如果这是一个愚蠢的问题 我对此很陌生 我应该如何将组合框添加到数据表 然后将其加载到数据网格视图中 这可以做到吗 这是最好的方法吗 非常感谢有关如何执行此操作的提示和教程 先感谢您 string columnNames dataTab

  • Google Colab 上 R-Keras 的工作流程 [重复]

    这个问题在这里已经有答案了 我想用 R 进行机器学习 请接受我的选择 并且想知道我是否可以使用 google colab 上的 IRkernel 来安装和运行 keras 从而以任何方式访问 TensorFlow 库 是否有一个有效 可访问

  • 基于索引列合并数据帧[重复]

    这个问题在这里已经有答案了 我可以看到我想做的事情是可以通过concat 合并索引上的数据帧 https stackoverflow com questions 21923880 merge dataframes on index 为什么我

  • Python 循环遍历文件夹并重命名文件

    我试图浏览一堆文件夹并进入每个文件夹并将特定文件重命名为不同的名称 我只是陷入了文件夹循环部分 我的文件系统如下所示 Root Directory Folder File1 File2 File3 Folder File1 File2 Fi

  • 将 pandas 中的通话数据拆分为 15 分钟间隔

    我是 python 和 pandas 的新手 尽管我研究了很多关于间隔的知识 但我找不到任何解决我的问题的方法 我希望有人可以提供帮助 这是我的 DF 示例 df pd DataFrame data Mel Gibson German 20

  • Laravel 混合版本控制不会删除旧的构建文件

    我正在使用 Laravel 5 4 和 mix 来版本化我的 javascript 和 scss 文件 问题是 它不会清除以前构建的文件 而只是添加一个具有不同文件名的新文件 即app 9d3e179e85922aad6ccf js 在我开

  • Go 中的符号 [:] 是什么意思？

    我在一些代码中发现了这一点 h s Hash tx sig err crypto Sign h prv 什么是 意思是 如果这是数组的完整切片 为什么不传递数组本身呢 这是什么编码风格 我想知道 在Go中 数组和切片略有不同 不能互换使用

  • AJAX 分页后的 WordPress 类别

    我真的很难找到一种方法来使用 ajax 为我的 WordPress 帖子创建分页 我找到的解决方案不起作用 要获得更多信息 这里有一个链接 底部有用于分页的项目符号 单击这些按钮后 我希望网站能够加载新帖子而不触发页面刷新 http max

  • 填充 va_list

    有没有办法创建一个va list从头开始 我正在尝试调用一个需要va list作为参数 func void entry int num args va list args char key 来自不接受可变数量参数的函数 我能想到的唯一方法是

  • 信号无法通过 execv() 正确重新启用

    我正在为我正在开发的 Linux 发行版编写一个系统关键程序 它需要在收到某些信号时自行重新启动 以避免崩溃 问题是 重新启动后 我无法重新启用该信号 也就是说 信号不能被接收两次 execv 自身执行后 当新进程调用 signal 来设置

  • 简单不平衡搜索树的平均渐近深度是多少？

    对于平衡搜索树 所有情况都是 O log N 对于不平衡搜索树 最坏情况是 O N 例如插入 1 2 3 4 最好情况复杂度是平衡时 例如插入 6 4 8 3 5 7 我们如何定义不平衡搜索树的平均情况复杂度 二叉树的平均高度为 Theta

热门标签