程序员经验分享-hwhale

O(1) 和 θ(1) 有什么区别？

2023-11-23

我知道它们的定义，但是为什么我有时在教科书上看到O(1)，有时看到θ(1)？

Thanks.


如果您谈论的是实数函数，则 O(1) 和 θ(1) 不一定相同。例如，考虑函数 f(n) = 1/n。该函数的复杂度为 O(1)，因为对于任何 n ≥ 1，f(n) ≤ 1。然而，它是notθ(1) 的原因如下：f(n) = θ(g(n)) 的一个定义是 |f(n) / g(n)| 的极限当 n 趋向无穷大时，某个有限值 L 满足 0

希望这可以帮助！

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

bigo

complexitytheory

O(1) 和 θ(1) 有什么区别？ 的相关文章

  • Python 将列表转换为集合，大 O

    感谢您的帮助 words Big list of words words set set words 当 n len words 时 我很难确定 set words 的复杂性是多少 是 O n 因为它在列表的所有项目上移动 还是 O l n

  • unordered_set::find 的复杂性可以预测吗？

    在寻找适合我正在构建的应用程序的容器时 我浏览了以下文档unordered set 鉴于我的应用程序通常只需要insert and find函数 这个类看起来相当有吸引力 然而 我有点推迟了 因为find是 O 1 摊销 但最坏情况是 O

  • 是否有用于平面度测试的在线算法？

    我知道平面度测试 http en wikipedia org wiki Planarity testing可以在 O v 相当于 O e 因为平面图有 O v 条边 时间内完成 我想知道是否可以在 O 1 摊销时间内在线完成 因为添加每个边

  • 集合运算的复杂性

    这就是我正在做的 字符串一 某个字符串 字符串二 某个字符串 我想知道字符串中的所有字符one and two它们应该按第一串中的顺序排列 我编写了一个 Java 程序 它通过使用 Collections 对两个集合执行设置操作 我想知道执

  • 这个计算 a^n 的算法是如何重写以在 O(log n) 时间内运行的？

    Suppose you want to compute an A simple algorithm would multiply a n times as follows result 1 for int i 1 i lt n i resu

  • 3d 表面的凸包算法 z = f(x, y)

    我有一个以一组三元组 x i y i z i 形式给出的 3D 表面 其中 x i 和 y i 大致位于网格上 并且每个 x i y i 都有一个关联的 z i 值 典型的网格是20x20 我需要在给定的公差范围内找到哪些点属于曲面的凸包

  • 寻找最接近的斐波那契数列

    我正在尝试解决一个更大的问题 并且我认为该程序的重 要部分花费在低效的计算上 我需要计算给定数字 N 的区间 P Q 其中 P 是 到 N 的最小斐波那契数 目前 我正在使用地图来记录斐波那契数的值 查询通常涉及搜索最多 N 的所有斐波那契

  • 如何交错或创建两个字符串的唯一排列（无需递归）

    问题是打印两个给定字符串的所有可能的交错 所以我用 Python 编写了一个工作代码 其运行如下 def inter arr1 arr2 p1 p2 arr thisarr copy arr if p1 len arr1 and p2 le

  • Google Chrome 中 array.splice() 的时间复杂度是多少？

    如果我使用 splice 从数组中删除一个元素 如下所示 arr splice i 1 这会是O n 在最坏的情况下 因为它会移动 i 之后的所有元素 或者它是常数时间 下面有一些链表魔法 最坏的情况下should be O n 复制所有n

  • for循环内递归函数的时间复杂度

    如果我们有一个函数 int x 0 int fun int n if n 0 return 1 for int i 0 i

  • 在未排序的整数列表中最优搜索 k 个最小值

    我刚刚接受采访时提出了一个问题 我很好奇答案应该是什么 问题本质上是 假设您有一个包含 n 个整数的未排序列表 您如何找到此列表中的 k 个最小值 也就是说 如果您有一个 10 11 24 12 13 列表并且正在寻找 2 个最小值 您将得

  • 使用FFT算法计算

    给定在平面上的点 1 0 2 0 n 0 上发现的一组 n 个粒子电荷载流子 在 i 0 点发现的粒子电荷记为 Qi 作用在粒子上的力由以下公式给出 C is a Coulomb s constant 给出一个算法来计算 Fi 对于总复杂度

  • 字符串排序真的是 O(n^2logn) 吗？ [复制]

    这个问题在这里已经有答案了 我读了以下内容 排序需要 O NlogN 那么它怎么是 O N 2logN 我们在这里想念的是 两个字符串的比较不是 O 1 在最坏的情况下 需要 在 所以最终的复杂度是O N 2logN 它是否正确 我一直认为

  • 如何确定算法函数的复杂度？

    您如何知道算法函数对于特定操作是否需要线性 常数 对数时间 它取决于CPU周期吗 您可以通过三种方式 至少 做到这一点 在网上查找算法 看看它是如何描述其时间复杂度的 根据输入大小 自己检查算法 查看嵌套循环和递归条件等内容 以及每个循环运

  • 具有多个退出点的代码段的循环复杂度

    我有这个验证密码的方法 Checks if the given password is valid param password The password to validate return code true if the passwo

  • 了解嵌套循环将运行多少次

    我试图了解下面的代码中语句 x x 1 作为 n 的函数执行了多少次 for i 1 i lt n i for j 1 j lt i j for k 1 k lt j k x x 1 如果我没记错的话 第一个循环就会被执行n次 还有第二次n

  • 在小于 O(n) 的时间内检查凸多边形交集？

    我有 2 个凸多边形 2d 我想检查这 2 个多边形是否相交 事实上 我会多次移动和旋转多边形 所以我也可以做一些预计算来获得这个问题的快速答案 我正在寻找一种低复杂度的算法 我知道可以检查一个点是否位于 O log n 的凸多边形中 我想

  • 求从1到N的所有数字的数字之和[重复]

    这个问题在这里已经有答案了 问题 求1到N 包括两端 所有数字的数字之和 时间复杂度应该是 O logN 对于 N 10 总和为 1 2 3 4 5 6 7 8 9 1 0 46 对于 N 11 总和为 1 2 3 4 5 6 7 8 9

  • 如何解决素数函数的大O表示法？

    我正在尝试理解 Big O 表示法 很抱歉 如果我问的问题太明显了 但我似乎无法理解这一点 我有以下 C 代码函数 我正在尝试为其计算 Big O 表示法 for i 2 i lt 100 i for j 2 j lt i j j if i

  • 关于大O和大Omega的问题

    我认为这可能是一个关于大 O 表示法的初学者问题 举例来说 我有一个算法 可以递归地分解整个列表 O n 然后将其重新组合在一起 O n 我假设这意味着效率为 O n O n 这是否可以简化为 2O n O 2n 或 O n 根据我对这种表

随机推荐

  • Symfony 4 - KnpPaginator Bundle“找不到服务，即使它存在于应用程序的容器中”

    我一直在关注教程 所有说明都显示它是以完全相同的方式完成的 但它似乎在 Symfony 4 中不起作用 是否有我忽略的东西 或者捆绑包根本不兼容 I ran composer require knplabs knp paginator bu

  • 如何使用 jest 和 React 测试库测试调用提交表单的按钮

    所以我试图测试 onSubmit 函数是否在单击按钮时被触发 我这样做的方式是通过测试 onSubmit 函数的内部正在获取调用 axios post 方法 the test describe RecipeSearch gt test su

  • 关于Android中SQLite数据库游标的几个问题

    为了在我的应用程序中实现数据库访问 我遵循拉尔斯 沃格尔教程 但我对一些事情感到非常困惑 每次拨打电话时fetchTodo将创建并返回一个新游标 将前一个光标留给垃圾收集器 所以 如果我不使用startManagingCursor甚至是Cu

  • Android 应用程序中的 API 密钥等敏感全局信息存储在哪里？

    我需要在 Android 应用程序中存储一些敏感信息 如果我将其放入资源文件中 则其他应用程序只需使用以下命令即可浏览和读取该文件似乎是微不足道的PackageManager getResourcesForApplication 放置此类信

  • sqlalchemy，用DSN指定数据库名称

    我正在尝试使用以下命令从 Linux 连接到 SQL Serversqlalchemy 这一页显示基于 DSN 的连接 如下所示 engine create engine mssql pyodbc scott tiger some dsn

  • 如何让 PHP 回显 XML 标签？

    我正在开发一个具有大约 3 000 4 000 个动态生成页面的网站 并且我希望更新 XML 站点地图 我过去曾尝试使用在线生成器 但它们似乎从未正确捕获所有页面 所以我打算自己做一些事情 基本上我有类似的东西

  • 如何使用 AutoFac 解析正确的记录器类型？

    我正在更新一个使用 AutoFac 的遗留项目 并且我想将 NLog 与 Simple Logging Facade SLF 结合使用 我过去曾在 Ninject 中使用过它 它的设置非常简单 我只需要执行以下操作 kernel Bind

  • 如何在 JavaScript 中匹配整个单词？

    我试图通过文本框搜索整个单词 假设我搜索 me 我应该找到文本中所有出现的 me 一词 但不能找到 memmm 我正在使用 JavaScriptsearch my regex expression 执行当前搜索 没有成功 经过多次提议使用

  • 没有 chroot 的 LXC

    有没有办法在不创建容器的情况下使用LXC使用进程组进行资源管理 我正在开发一个在沙箱内运行任意代码的服务 我只对硬件资源管理感兴趣 我不想进行任何 chrooting 我只希望这些进程组能够访问主文件系统 有人告诉我 lxc 是轻量级的 但

  • arm-none-eabi-ld：找不到-lc

    我正在尝试为基于 XMC1100 的开发板编写代码 我正在尝试这个教程 http eleceng dit ie frank arm BareMetalXMC2Go index html 我已经下载了blinky tar gz 文件并解压 当

  • 使用 ssl 公钥/私钥基于 Web 登录？

    是否可以通过网络浏览器创建需要公钥 私钥的登录过程 公钥将存储在服务器上 私钥将由用户保存 并加密 我基本上想做一些类似于 SSH 的事情 但是通过网络 也许是 HTTP 身份验证的自定义方法 摘要 除外 我知道使用普通浏览器可能无法做到这

  • 使用数据库表中的值生成下拉列表输入

    我正在尝试使用 Laravel 生成一个包含 MySQL 表中的值的下拉列表 表格很简单 两列 id and category 以下将检索所有记录 类别 但返回一个对象而不是数组 这是我需要的下拉代码 categories Category

  • 如何在Python中制作n维嵌套for循环？ [复制]

    这个问题在这里已经有答案了 我有以下情况 for x1 in range x1 x2 for x2 in range x3 x4 for x3 f x1 x2 x3 如何将其转换为我只告诉 python 的机制n变量名称为 x1 x2 x3

  • 检测这是 iframe 加载还是直接加载

    我希望仅在 iframe 内的页面上拉出表单时才显示该表单 我怎么做 有服务器端解决方案吗 如果您使用 JQuery 安装说明如下 http jquery com document ready function if window wind

  • 指针和引用作为 const 对象的成员变量

    以下代码编译良好 不过我想知道它是否是合法的C 更具体地说 如果我有一个 const 对象 我是否可以通过该对象的指针 引用修改变量 class Foo public int a int b Foo int a int b a a b b

  • 关于Python日志记录中的NOTSET

    As the logger setLevel医生说 创建记录器时 级别设置为 NOTSET 这会导致当记录器是根记录器时处理所有消息 或者当记录器是非根记录器时将委托给父记录器 请注意 根记录器是使用 警告 级别创建的 所以我想如果我创建一

  • Angular：为什么 CSS 对齐不能与 ng-repeat 一起使用？

    我正在尝试做什么 我正在尝试均匀分布li in a ul 证明合法 当我硬编码时 CSS 可以工作li 但是当我使用ng repeat 不再应用CSS HTML div div ul class two column li li li li

  • Postgres 在全局范围内设置自动提交关闭

    如何在 psql 8 4 中全局级别设置自动提交 是否有一个我可以更改的配置属性 它将为集群上的所有数据库引入此行为 以在关闭自动提交的情况下启动数据库会话 只需添加以下内容即可 psqlrc set AUTOCOMMIT off 请注意

  • Dockerfile CMD“未找到命令”

    我有以下内容Dockerfile FROM nodesource node jessie ADD SOMEPATH RUN cd SOMEPATH npm install WORKDIR SOMEPATH CMD bash npm run

  • O(1) 和 θ(1) 有什么区别？

    我知道它们的定义 但是为什么我有时在教科书上看到O 1 有时看到 1 Thanks 如果您谈论的是实数函数 则 O 1 和 1 不一定相同 例如 考虑函数 f n 1 n 该函数的复杂度为 O 1 因为对于任何 n 1 f n 1 然而 它

热门标签