big-o相关内容

为什么在链表中间插入 O(1)?

根据维基百科关于链表的文章，在链表被认为是 O(1).我认为它会是 O(n).您不需要定位可能靠近列表末尾的节点吗? 这个分析是否不考虑节点操作的发现(尽管它是必需的)和插入本身? 编辑: 链表与数组相比有几个优点.在列表的特定点插入元素是一个恒定时间操作，而在数组中插入可能需要移动一半或更多元素. 上面的说法有点误导我.如果我错了，请纠正我，但我认为结论应该是: 数 ..

发布时间：2022-01-01 18:04:33 linked-list big-o 其他开发

.NET 集合类的渐近复杂性

有没有关于.NET集合类(Dictionary、List代码> 等等...)? 我知道 C5 库的文档包括一些关于它的信息(example)，但我也对标准的 .NET 集合感兴趣......(PowerCollections 的信息也很好). 解决方案 MSDN 列出了这些: 字典 列表 SortedList(编辑:错误链接；这是通用版本) SortedDictionar ..

发布时间：2021-12-27 17:45:07 .net collections big-o asymptotic-complexity C#/.NET

当用作散列时，JavaScript 数组的大 O 是什么?

当用作散列时，JavaScript 的数组访问的大 O 是什么? 例如 var x= [];for(var i=0; i 希望 JS 引擎不会在内部使用 O(n) 的线性搜索，但这是确定的吗? 解决方案 在 JavaScript 中访问对象属性和数组元素在语法上假定在 恒定时间:O(1).ECMAScript 规范不保证性能特征，但所有现代 JavaScript 引擎都在恒定时间 ..

发布时间：2021-12-27 16:28:35 javascript hash hashtable big-o 前端开发

了解 Dijkstra 算法的时间复杂度计算

根据我的理解，我使用下面给出的邻接列表将 Dijkstra 算法的时间复杂度计算为大 O 表示法.它没有像预期的那样出现，这让我一步一步地理解它. 每个顶点都可以连接到 (V-1) 个顶点，因此每个顶点的相邻边的数量是 V - 1.假设 E 表示连接到每个顶点的 V-1 个边. 寻找和更新最小堆中每个相邻顶点的权重为 O(log(V)) + O(1) 或 O(log(V)). 因此从上面 ..

发布时间：2021-12-24 14:30:47 algorithm graph big-o time-complexity dijkstra 其他开发

如果我们使用链表实现桶，桶排序的复杂度是 O(n+k) 吗?

如果我们使用链表实现的桶，我很好奇为什么桶排序的运行时间是 O(n + k).例如，假设我们有这样的输入: n = 元素数 = 8k = 范围 = 3数组 = 2,2,1,1,1,3,1,3 桶看起来像这样: 1: 1 ->1 ->1 ->12: 2 ->23: 3 ->3 插入这些桶所花费的总时间是 O(n)，假设我们在链表中存储了一个尾指针. 要删除，我们必须转到每个存储桶，然后 ..

发布时间：2021-12-22 08:27:18 algorithm sorting data-structures big-o 其他开发

索引、插入和删除常见数据结构的时间复杂度是多少?

对于最常见的数据结构(包括数组、链表、哈希表等)的操作，没有可用的大 O 表示法的摘要. 解决方案 关于这个主题的信息现在可以在维基百科上找到:搜索数据结构 +------------------------+---------+------------+-----------+--------------+||插入 |删除 |搜索 |空间使用 |+--------------+---- ..

发布时间：2021-12-22 08:26:41 data-structures complexity-theory big-o 其他开发

如何在 O(n) 时间内对单向链表进行二分搜索?

这个较早的问题谈到在 O(n) 时间内对双向链表进行二分搜索.该答案中的算法如下: 转到列表中间进行第一次比较. 如果它等于我们正在寻找的元素，我们就完成了. 如果它比我们要查找的元素大，则向后走一半到起点并重复. 如果它比我们要查找的元素小，则向前走一半到起点并重复. 这对于双向链表非常有效，因为它可以向前和向后移动，但这种算法在单向链表中不起作用. 是否可以在单向链表而 ..

发布时间：2021-12-22 08:20:17 algorithm data-structures linked-list big-o binary-search 其他开发

如何在 O(n) 时间内对双向链表进行二分搜索?

我听说可以在 O(n) 时间内对双向链表进行二分查找.访问双向链表的随机元素需要 O(n) 时间，而二分查找访问 O(log n) 个不同元素，那么运行时间不应该是 O(n log n) 吗? 解决方案 从技术上讲，双向链表二分查找的运行时间是 O(n log n) 是正确的，但这并不是一个严格的上限.使用稍微更好的二分搜索实现和更聪明的分析，可以让二分搜索在 O(n) 时间内运行. ..

发布时间：2021-12-22 08:12:55 algorithm data-structures big-o binary-search doubly-linked-list 其他开发

为什么哈希图查找是 O(1)，即恒定时间?

如果我们从 Java 的角度来看，那么我们可以说 hashmap 查找需要恒定的时间.但是内部实现呢?它仍然需要在特定的桶中搜索不同的匹配键(匹配哪个键的哈希码).那么为什么我们说哈希图查找需要恒定时间?请解释. 解决方案 在所使用的哈希函数的适当假设下，我们可以说哈希表查找需要 预期 O(1) 时间(假设您使用的是标准散列方案，如线性探测或链式散列).这意味着平均，哈希表执行查找的工作量 ..

发布时间：2021-12-22 00:04:06 data-structures hash hashmap hashtable big-o 其他开发

python集合操作的时间复杂度?

python 在 Big O 表示法中的每个集合操作的时间复杂度是多少? 我正在使用 Python 的 set type 进行大量操作项.我想知道每个操作的性能将如何受到集合大小的影响.例如，添加，以及成员资格测试: myset = set()myset.add('foo')'foo' 在 myset 谷歌搜索没有找到任何资源，但仔细考虑 Python 集合实现的时间复杂度似乎是合理的. ..

发布时间：2021-12-21 23:58:29 python data-structures set complexity-theory big-o Python

什么是大 O 符号?你使用它吗?

什么是大 O 符号?你会用吗? 我想我错过了这门大学课程:D 有没有人使用它并举出一些他们使用它的真实例子? 另见: 八岁儿童的大O? Big O，你是如何计算/近似的? 您是否在现实生活中应用了计算复杂性理论? 解决方案 大多数人在谈论 Big-O 时忘记了一件重要的事情，因此我觉得有必要提一下: 您不能使用 Big-O 来比较两种算法的速度.Big-O ..

发布时间：2021-12-20 16:02:16 optimization complexity-theory big-o 其他开发

在 O(K*log(K)) 中打印给定堆中最大的 K 个元素?

鉴于以下问题，我不完全确定我当前的解决方案: 问题: 给定一个包含 n 个元素的最大堆，它存储在一个数组 A 中，是否可以打印所有最大的 K 个元素在 O(K*log(K)) 中? 我的回答: 是的，因为搜索元素需要 O(log(K)) ，因此这样做 对于 K 元素需要 O(K * log(K)) 运行时间. 解决方案 这在最大堆中是可能的，因为您只是从树中打 ..

发布时间：2021-12-20 14:00:17 algorithm search tree heap big-o 其他开发

比 O(n) 更好的范围交集算法?

范围交集是一个简单但重要的问题. 它已经被回答了两次: 查找数字范围交集 比较日期范围 第一个解决方案是 O(n)，第二个解决方案是针对数据库(当然小于 O(n)). 我有同样的问题，但是对于一个很大的 n 并且我不在数据库中. 这个问题好像很像存储二维点以快速检索矩形内的点，但我看不到它是如何映射的. 那么你会用什么数据结构来存储这组范围，使得对范围的搜索成 ..

发布时间：2021-12-20 13:58:52 java algorithm search big-o interval-intersection Java开发

是大 O(logn) 对数基数 e 吗?

对于二叉搜索树类型的数据结构，我看到大 O 表示法通常记为 O(logn).对数中的小写“l"是否意味着自然对数所描述的以 e (n) 为底的对数?抱歉问了一个简单的问题，但我总是无法区分不同的隐含对数. 解决方案 一旦用 big-O() 表示法表示，两者都是正确的.然而，在O()多项式的推导过程中，在二分搜索的情况下，只有log2是正确的.我认为这种区别是您提出问题的直观灵感. 此 ..

发布时间：2021-12-17 14:50:41 math binary-tree complexity-theory big-o 其他开发

递归应用于 Python 中的列表与树

我对递归的主要关注是 Python 中的递归限制，我认为是 1000.考虑到这一点，我想讨论两种情况: 场景 1:对平衡树(二进制)应用递归 例如搜索树中的最大值: class 节点:def __init__(self, value, left=None, right=None):self.value = 价值self.left = 左self.right = 正确定义最大值(根): ..

发布时间：2021-12-16 08:59:12 python recursion big-o space-complexity Python

为什么计算斐波那契数列的复杂度是 2^n 而不是 n^2?

我试图使用递归树找出斐波那契数列的复杂度，并得出树的高度 = O(n) 最坏情况，每个级别的成本 = cn，因此complexity = n*n=n^2 怎么是O(2^n)? 解决方案 一个朴素的递归斐波那契数列的复杂度确实是 2ⁿ. T(n) = T(n-1) + T(n-2) = T(n-2) + T(n-3) + T(n-3) + T(n-4) == T(n-3) + T(n ..

发布时间：2021-12-16 08:24:26 algorithm recursion big-o fibonacci 其他开发

确定递归函数的复杂度(大 O 表示法)

我明天有一个计算机科学期中考试，我需要帮助确定这些递归函数的复杂性.我知道如何解决简单的案例，但我仍在努力学习如何解决这些更困难的案例.这些只是我无法弄清楚的一些示例问题.任何帮助将不胜感激，并将极大地帮助我的学习，谢谢！ int recursiveFun1(int n){如果 (n 解决方案 每个函数的时间复杂度，用 Big O 表示法: int recursiveFun1(int n ..

发布时间：2021-12-16 08:09:58 recursion big-o complexity-theory 其他开发

IF 如何影响复杂性?

假设我们有一个包含 1.000.000 个元素的数组，我们遍历所有元素以检查一些简单的东西，例如第一个字符是否为“A".根据我(很少)的理解，复杂度将是 O(n) 并且需要一些 X 时间.如果我添加另一个 IF(不是 else if)来检查，比方说，如果最后一个字符是“G"，它会如何改变复杂性?它会使复杂性和时间加倍吗?像 O(2n) 和 2X? 我想避免考虑不同命令必须进行的计算数量.例如 ..

发布时间：2021-12-12 13:55:45 if-statement complexity-theory big-o 其他开发

Python 字典键.“在"复杂

快速提问，主要是满足我对这个话题的好奇心. 我正在编写一些带有 SQlite 数据库后端的大型 Python 程序，将来会处理大量记录，因此我需要尽可能多地优化. 对于一些函数，我正在字典中搜索键.我一直在使用“in"关键字进行原型设计，并计划稍后返回并优化这些搜索，因为我知道“in"关键字通常是 O(n)(因为这只是转换为 python 迭代整个列表并进行比较每个元素).但是，由于 ..

发布时间：2021-12-10 16:06:11 python dictionary hashmap complexity-theory big-o Python

快速排序优于堆排序

堆排序的最坏情况复杂度为O(nlogn)，而快速排序的复杂度为O(n^2).但经验证据表明，快速排序更胜一筹.这是为什么? 解决方案 主要因素之一是快速排序具有更好的引用局部性 -- 下一个要访问的东西通常在内存中很近到你刚才看的东西.相比之下，堆排序跳得更多.由于靠近的事物可能会被缓存在一起，因此快速排序往往会更快. 然而，快速排序的最坏情况性能明显比堆排序差.由于某些关键应用程序 ..

发布时间：2021-12-10 10:50:57 algorithm sorting big-o quicksort heapsort 其他开发