Big O:如何根据外部 for 循环确定 for 循环增量的运行时间?

2024-02-18

我有以下算法,运行时复杂度为 O(N^2) 但我想对其有更深入的了解,而不是仅仅记住常见的运行时。

分解和分析它的正确方法是什么i+1考虑在内层 for 循环中吗?

void printunorderedPairs(int[] array) {
    for(int i=0; i<array.length; i++) {
        for(int j=i+1; j<array.length; j++) {
            System.out.println(array[i] + "," + array[j]);
        }
    }
}

EDIT

询问如何分析特定问题


分解和分析它的正确方法是什么

拿起铅笔和纸,放下一些展开的环:

     i        inner loops per i
-------------------------------
     1               length - 1  
     2               length - 2
    ..                       ..  
     k               length - k 
    ..                       ..
length - 1                    1
length                        0

现在,为了获得所需的总时间,我们对内部循环进行总结:

 (length - 1) + (length - 2) + ... + (length - k) ... + 1 + 0

这是一个算术级数,它的和是

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

Big O:如何根据外部 for 循环确定 for 循环增量的运行时间? 的相关文章

  • 算法 - 如何有效删除列表中的重复元素?

    有一个list L 它包含以下元素任意类型each 如何有效删除此类列表中的所有重复元素 必须保留订单 只需要一个算法 因此不允许导入任何外部库 相关问题 在Python中 从列表中删除重复项以使所有元素都是唯一的最快算法是什么在维持秩序的
  • 用于整数分区的优雅 Python 代码 [关闭]

    Closed 这个问题需要多问focused help closed questions 目前不接受答案 我尝试编写代码来解决标准整数分区问题 维基百科 http en wikipedia org wiki Partition 28numb
  • 找到质数?

    为了判断 N 是否是质数 我们只需要查找所有小于或等于 sqrt N 的数字 这是为什么 我正在编写 C 代码 因此试图理解其背后的原因 如果 N 是一个正整数 且能被两个正整数 1 和 N 整除 则 N 是素数 由于数字的约数不能大于该数
  • 关于大O和大Omega的问题

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

    我正在尝试编写一个Java程序来计算大数的阶乘 它似乎BigInteger无法容纳这么大的数量 下面是我编写的 简单的 代码 public static BigInteger getFactorial BigInteger num if n
  • 给定一个点向量(可能无序),找到多边形(不是凸包)

    我目前有一个点向量 vector
  • 数组中最远的相等元素

    假设你有一个未排序的数组 你如何找到两个相等的元素 使它们成为数组中最远的元素 例如8 7 3 4 7 5 3 9 3 7 9 0ans 将是7 9 7 1 8 我想到了以下几点 initialise max 0 using hashing
  • 如何在单向链表(一次遍历中)中从尾部获取第 n 个节点?

    所以我在一次考试中得到了这个问题 如何从单链表的尾部获取第 n 个节点 每个节点都有一个值和一个下一个 指向下一个值的指针 我们得到这个 getNodeFromTail Node head int x 所以我的做法是通过遍历一次来求出列表的
  • 运行时间为 O(n) 且就地排序的排序算法

    有没有运行时间为O n 并且还分类到位 在某些情况下 最好的情况是 O n 但这可能是因为项目集合已经排序 你正在看 O nlogn 一些较好的平均值 话虽如此 排序算法的 Wiki 还是相当不错的 有一个表格比较了流行的算法 说明了它们的
  • 如何检查无向图是否有奇数环

    我试图找到一个 O V E 时间算法来检查是否已连接 无向图有或没有奇数环 我正在考虑对图进行广度优先搜索 并尝试将顶点标记为黑色和白色 以便没有两个标记为相同颜色的顶点相邻 是否有任何已知的更简洁的算法可以在线性时间内解决这个问题 你的方
  • 当平方和为N时,如何找到四个变量的所有可能值?

    A 2 B 2 C 2 D 2 N给定一个整数N 打印出整数值的所有可能组合ABCD求解方程 我猜我们可以比暴力做得更好 天真的暴力会是这样的 n 3200724 lim sqrt n 1 for a 0 a lt lim a for b
  • 填充体积算法

    我有一个具有一定尺寸长度 宽度 高度的盒子 我有不同长度 宽度 高度的物品 是否有现有的算法可以确定放入盒子中的最佳物品 这称为装箱 切割库存 背包问题 并且是 NP 难问题 一般来说 您只能通过使用启发式方法获得近似解 请参见示例 htt
  • 一种良好且简单的随机性测量方法

    获取一长整数序列 例如 100 000 个 并返回序列随机性的测量值的最佳算法是什么 该函数应返回单个结果 如果序列并非完全随机 则返回 0 如果完全随机 则返回 1 如果序列有点随机 它可以给出介于两者之间的东西 例如0 95 可能是一个
  • 如何在 JavaScript 中构建树模式匹配算法?

    好吧 这是一个有点复杂的问题 但是 tl dr 基本上是如何使用 模式树 解析 实际树 如何检查特定的树实例是否与特定的模式树匹配 首先 我们有我们的结构模式树 模式树通常可以包含以下类型的节点 sequence节点 匹配一系列项目 零个或
  • 在android中的webview中运行时更改URL

    我创建了一个小程序 可以在 webview 中加载特定网站 我想密切关注 URL 如果 URL 包含 xxx 单词 那么它应该导航到另一个页面 例如 如果我设置 www example com 我现在可以导航到 www example co
  • 定点数学比浮点运算快吗?

    多年前 即 20 世纪 90 年代初期 我构建了图形软件包 该软件包基于定点算术和预先计算的 cos sin 表格以及使用牛顿近似方法进行 sqrt 和对数近似的缩放方程来优化计算 这些先进技术似乎已经成为图形和内置数学处理器的一部分 大约
  • 自动跟踪算法

    我正在尝试写一个simple跟踪例程来跟踪电影中的某些点 本质上我有一系列 100 帧长的电影 在黑暗背景上显示一些亮点 我每帧有大约 100 150 个点 它们在电影的过程中移动 我想跟踪它们 所以我正在寻找一些有效的 但可能不会过度实施
  • “包含字符串”的快速索引

    在我的应用程序中 我有多达数百万个短字符串 大部分短于 32 个字符 我想实现一个带有附加列表的搜索框 该列表仅包含包含在搜索框中输入的整个字符串的元素 如何预先建立索引来快速找到此类字符串 所有排序的 STL 容器都会检查整个字符串 对于
  • LRU算法,实现这个算法需要多少位?

    我有一个关于 LRU 算法的小问题 如果您有一个包含四个块的高速缓存 那么需要多少位来实现该算法 假设您指的是 4 路组关联缓存 完美 LRU 本质上是按照使用顺序为每一行分配一个精确的索引 您也可以将其视为 年龄 因此 4 个元素中的每一
  • 为什么这个算法的Big-O复杂度是O(n^2)?

    我知道这个算法的大O复杂度是O n 2 但我不明白为什么 int sum 0 int i 1 j n n while i lt j sum 即使我们设定了j n n一开始 我们在每次迭代期间递增 i 并递减 j 因此最终的迭代次数不应该比n

随机推荐

  • 使用 Google Maps Javascript API 在我自己的图像上进行捏合缩放

    我正在尝试创建一个适合移动设备的网页 允许用户拖动 img 周围在一个 div 我已经使用了这个工作image ontouchstart方法 现在我想要做到这一点 以便用户在从 iOS 设备查看此内容时可以进行捏合缩放 我当前正在从 iPa
  • 如何配置oauth回调的路由

    我正在使用宝石OAuth2 https github com intridea oauth2与 Google 服务进行通信 我不明白如何实现回调 该回调接收带有 OAuth 代码的响应以获取访问令牌 当我在中设置断点时callback方法
  • 我们可以在 Firestore 中查询多深? [关闭]

    Closed 这个问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 我只是在寻找在 Firestore 上设计数据库的答案 我有根集合的 4 级和 5 级子集合 在这个级
  • Azure 发布管道错误:无法获取 Kudu 应用程序设置。错误:服务暂时不可用(代码:503)

    我有一个 Azure DevOps 发布管道 它将容器部署到 Azure 中的应用程序服务 当我运行它时 部署容器的任务失败并显示消息 2020 10 23T16 12 20 8516547Z 错误 错误 无法获取 Kudu 应用程序设置
  • 使用 Hudson 发布 NUnit 测试结果报告时出现问题

    我在 Hudson 和 NUnit 测试方面遇到问题 当尝试发布 NUnit 的测试结果报告时 Hudson 中的选项 即 发布 NUnit 测试结果报告 会产生问题 我无法提供作业工作区文件夹下已创建的 XML 文件的路径 当我设置文件的
  • 如何配置 persistence.xml 提供者标签

    嘿 我正在学习这些东西 我并没有真正理解所有内容 而且我有一个问题 我不知道在 persistence xml 的提供者标签中写什么 这是我的 persistence xml 和 pom xml 文件 pom xml
  • 如何在运行时将图像加载到WPF?

    在运行时将图像加载到 WPF 窗口似乎相当复杂 Image image image new Uri Bilder sas png UriKind Relative Source new BitmapImage image 我正在尝试这段代码
  • 带百分比标签的 Ggplot 堆积条形图

    I am trying to do a stacked bar plot based on count but with the labels showing the percentage on the plot I have produc
  • 如何在 C++ 中加载共享对象?

    我有一个共享对象 so Windows dll 的 Linux 等效项 我想将其导入并与我的测试代码一起使用 我确信这不是那么简单 但这就是我想做的事情 include headerforClassFromBlah h int main l
  • 如何在 QuickGraph Dijkstra 或 A* 中设置目标顶点

    我使用的是 QuickGraph 3 6 版 我找到了函数 SetRootVertex 但没有 SetTagretVertex 我需要这个 因为我正在巨大的图中搜索短路径 这会大大加快程序速度 有问题的类是 DijkstraShortest
  • C++ 错误:基函数受保护

    我想知道为什么下面的代码不能编译 class base protected typedef void base function type const void function impl const error void base fun
  • 优化字符串连接的聚合[关闭]

    Closed 这个问题需要细节或清晰度 help closed questions 目前不接受答案 Update 对于那些有幽默感的人 您可以假设无论传递给它什么函数 聚合仍然会产生正常结果 包括在被优化的情况下 我编写这个程序是为了构建一
  • DataContract,默认 DataMember 值

    有没有办法在反序列化期间选择不在 xml 文件中的属性的默认值 If the mAgexml 文件中不存在属性 我想使用默认值 18 这可能吗 DataContract public class Person public Person D
  • 如何将触摸事件从 UIView 传递到其下方的 UIView?

    一个简单的问题 但我找不到解决方案 我有 2 个 UIView 一个在同一个父视图中 一个在另一个之上 都有GestureRecognizers在它们上 但只有最顶层正在接收事件 我怎样才能让最上面的视图将他获得的所有手势传递给它下面的其他
  • Golang MySQL 错误 - packet.go:33: 意外的 EOF

    我将整个代码库从 PHP 切换到 Go 在运行的几个进程中 我随机收到此错误 mysql 2016 10 11 09 17 16 packets go 33 unexpected EOF 这是我的 db 包 它处理与数据库的所有连接 pac
  • 有人可以向我解释一些 helm 的用例吗?

    我目前正在使用 kubernetes 并且遇到了 helm 假设我不喜欢用与我的应用程序无关的进程 感染 我的 kubernetes 集群 但如果它有益的话 我很乐意接受 所以我做了一些研究 但我仍然找不到任何使用我的 yaml 描述符和
  • ASP.Net URL 编码

    我正在 ASP net 中实现 URL 重写 但我的 URL 给我带来了很多问题 URL 是根据部门和类别的数据库生成的 我希望员工能够使用任何合适的特殊字符将项目添加到数据库中 而不会破坏网站 我在构建 URL 之前对数据进行编码 有几个
  • Sphinx .net 实现

    是否可以在 net MSSQL 应用程序中实现Sphinx 全文搜索 如果是这样 任何帮助如何实现相同的 一个小的描述将会有很大帮助 我们正在使用 SphinxConnector NET http www sphinxconnector n
  • Zend Framework:需要ACL的典型示例

    有人可以指导我 ACL 的典型实施示例吗 就像 管理员 可以访问 管理 模块 用户 可以访问 用户模块 访客可以访问 打开 页面 我可以把我的 ACL 贴给你 它由三个元素组成 acl ini ACL 控制器插件 My Controller
  • Big O:如何根据外部 for 循环确定 for 循环增量的运行时间?

    我有以下算法 运行时复杂度为 O N 2 但我想对其有更深入的了解 而不是仅仅记住常见的运行时 分解和分析它的正确方法是什么i 1考虑在内层 for 循环中吗 void printunorderedPairs int array for i