程序员经验分享-hwhale

使用主定理求解递推式 T(n) = T(n / 2) + O(1)？ [关闭]

2024-01-11

我正在尝试解决递归关系，以找出使用主定理及其递归概念的算法的复杂性，我如何证明：

T(n) = T(n/2)+O(1)

is

T(n) = O(log(n)) ?

任何解释将不胜感激！


您的复发是

T(n) = T(n / 2) + O(1)

由于主定理适用于以下形式的递归

T(n) = aT(n / b) + nc

在这种情况下你有

  • a = 1
  • b = 2
  • c = 0

Since c = logba (since 0 = log2 1), you are in case two https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)#Case_2_example of the Master Theorem, which solves to Θ(nc log n) = Θ(n0 log n) = Θ(log n).

希望这可以帮助！

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

Algorithm

complexitytheory

bigo

recurrence

mastertheorem

使用主定理求解递推式 T(n) = T(n / 2) + O(1)？ [关闭] 的相关文章

  • 多项式时间复杂度中的负系数

    假设某些算法具有多项式时间复杂度T n 是否有可能任何一项的系数为负 直观上 答案似乎是明显的 否 因为任何算法都没有任何部分可以减少先前步骤所花费的现有时间 但我想确定一下 当谈论多项式复杂度时 只有次数最高的系数才有效 但我认为你可以有

  • 查找数组中的组合

    我在java中有一个像这样的二维数组 transmission communication tv television approach memorycode methodact 我需要获得所有组合 例如 transmission appr

  • 循环中的递归算法复杂度（运行时间）

    我想了解您对如何检测以下递归算法的 T n 运行时间 的意见 Charm 是一种用于发现事务数据库中频繁闭项集的算法 频繁闭项集列表是在一组交易 tids 中多次出现的频繁项 例如面包和牛奶是经常一起购买的物品 它们是通过将索引为 i 的当

  • 具有 3 路划分的快速排序

    什么是三向分区快速排序 画一个数组 3 5 2 7 6 4 2 8 8 9 0 A 两分区快速排序会选择一个值 比如 4 并将每个大于 4 的元素放在数组的一侧 将每个小于 4 的元素放在另一侧 就像这样 3 2 0 2 4 8 7 8 9

  • 如何找到给定顶点的所有多边形？

    我有一个顶点列表 并且我知道它们之间的连接 我试图找到顶点的所有多边形形状 这些多边形形状不应重叠 我做了一些研究 我认为如果我可以顺时针 或逆时针 没有区别 遍历顶点 我可以检测多边形形状 因此 我寻找顺时针遍历顶点的解决方案 我发现了一

  • 有人真正有效地实现了斐波那契堆吗？

    你们中有人曾经实施过斐波那契堆 http en wikipedia org wiki Fibonacci heap 几年前我就这样做了 但它比使用基于数组的 BinHeaps 慢了几个数量级 当时 我认为这是一个宝贵的教训 告诉我们研究并不

  • 在小于 O(N) 的时间内找出点是否位于 N 个（可能重叠）矩形之一内

    我有一个图像 我想在鼠标移动到某些矩形区域时显示工具提示 矩形区域最多可达 1000 个 但是 仅检查每个矩形中是否有点 时间复杂度为 O N 导致移动鼠标时界面无响应 有没有办法在小于 O N 的时间内完成它 我可以预先对矩形进行排序 我

  • 为什么路径压缩不会改变 UnionFind 中的排名？

    我正在研究 UnionFind 的实现 并从这里进行排序和路径压缩http en wikipedia org wiki Disjoint set data struct Disjoint set forests http en wikipe

  • 图中使用 K 个反向边的所有最短路径

    假设我有一个有向图 G V E 其边的权重为正整数 我需要做的是使用最多 K 整数 个反向边找到所有顶点之间的最短路径 我的意思是 如果我们在边 u 处 并且只有一条从 v 到 u 的有向边 只要我们没有在这条路径上使用 K 个反向边 我们

  • 增量决策树 C++ 实现

    有谁知道决策树分类器的增量实现吗 这样 当您将新实例添加到训练集中时 它可以根据现有决策树分类器以低计算量并尽可能快地生成最佳决策树分类器 换句话说 我有一个最优决策树分类器集A 其中命名为T 1 现在我想添加实例X to set A并找到

  • 使用按键重新排列字符串

    我想使用Pythonrandomly根据给定的键重新排列字符串的各个部分 我还想用相同的密钥恢复原始字符串 def rearrange key data pass def restore key rearranged data pass 效

  • Haskell：先进先出队列算法的复杂性

    这是我对 FIFO 队列的尝试 type Queue a a gt a empty Queue a empty id remove Int gt Queue a gt a Queue a remove n queue take n queu

  • GO中的优先级队列

    谁能向我解释一下 我想在GO中实现一个优先级队列 接口实现来自link https golang org pkg container heap example priorityQueue 但优先级最低 我的代码 pq make Priori

  • java中的散列是如何工作的？

    我正在尝试弄清楚java中的哈希值 例如 如果我想在哈希图中存储一些数据 它是否会有某种带有哈希值的底层哈希表 或者 如果有人能够对哈希的工作原理给出一个很好且简单的解释 我将非常感激 HashMap 基本上在内部实现为数组Entry 如果

  • 如何随机打乱地图中的值？

    我有一个 std map 其中键和值均为整数 现在我想随机打乱地图 因此键随机指向不同的值 我尝试了 random shuffle 但它无法编译 请注意 我并没有尝试洗牌键 这对于地图来说没有意义 我正在尝试随机化这些值 我可以将这些值推入

  • 将矩形分组到网格中

    我有一个随机切片的矩形网格 宽度为 80 单位 我已经将网格每一行的可用空间存储在如下数组中 pX 1 sX 15 pX 30 sX 13 pX 43 sX 1 pX 44 sX 17 pX 1 sX 15 pX 16 sX 14 pX 3

  • 快速算法可以快速找到一组范围中某个数字所属的范围？

    场景 我有几个数字范围 这些范围不重叠 由于它们不重叠 逻辑结果是任何时候任何数字都不能属于多个范围 每个范围都是连续的 单个范围内没有空洞 因此范围 8 到 16 将真正包含 8 到 16 之间的所有数字 但两个范围之间可能存在空洞 例如

  • 如何跟踪此对象图深度优先搜索算法中的深度？

    我有这段代码 它迭代一棵树 进行深度优先搜索 每个元素都只处理一次 非常好 void iterateOverTree TreeNode node NSMutableArray elements NSMutableArray array el

  • 动态规划二维平面算法的递归关系帮助

    所以我一直在研究一种算法 我想要完成的任务是 考虑一个 2D 平面 其中有随机分布在 y 上限和下限之间的目标 该集合为T T1 标有坐标 X Y 有一组 S 个传感器 保证覆盖每个目标 每个传感器的半径为 1 坐标为 X Y 每个目标都有

  • 为什么循环引导迭代算法的数组大小必须为 3^k+1？

    The 循环引导迭代算法 http www geeksforgeeks org an in place algorithm for string transformation 是一种通过将所有偶数项移至前面并将所有奇数项移至后面同时保留其相

随机推荐

热门标签