-
270 votesanswersviews
Big-O和Little-O表示法之间的区别
Big-O 符号 O(n) 和 Little-O 符号 o(n) 之间有什么区别? -
1 votesanswersviews
使用inorder后继方法打印BST的时间复杂度
我有一种方法可以在二进制搜索树(BST)中查找下一个inorder后继 . “inorderSuccessor”方法将BST的任何节点作为输入并输出下一个inorder后继 . 方法和树类定义如下: class BSTInorderSuccessor{ public static Node inorderSuccessor(Node node) { if (node.right !=... -
47 votesanswersviews
更糟糕的是更好 . 有一个例子吗?
是否存在一种广泛使用的算法,其时间复杂度比另一种已知算法的时间复杂度更差,但在所有实际情况下都是更好的选择( worse 复杂度,否则为 better )? 可接受的答案可能是以下形式: 算法A和B相应地具有O(N ** 2)和O(N)时间复杂度,但B具有如此大的常数,对于输入小于宇宙中的原子数量而言它没有优于A的优势 . Examples highlights from the answer... -
6 votesanswersviews
为什么在一般情况下,链排序为O(n sqrt n)?
我发现strand sort非常有吸引力,可以在常量空间中对单个链表进行排序,因为它比例如插入排序要快得多 . 我知道为什么它是 O(n) 在最好的情况下(列表已经排序)和 O(n^2) 在最坏的情况下(列表反向排序) . 但为什么 O(n sqrt n) 在平均情况下呢?如果算法不是基于二分法并且具有多项式最佳情况和最差情况性能,那么平均情况是 O(n^m) ,其中 m 是最佳情况的算术平均值'... -
2 votesanswersviews
选择排序,插入排序和快速排序的方案
如果有人能对我的逻辑给出一些意见,我会非常感激 . 对于所有键相同,选择排序或插入排序的数组,哪种方法运行得更快? 我认为这与数组已经排序时类似,因此插入排序将是线性的,选择排序是二次的 . 对于数组,哪种方法以相反的顺序,选择排序或插入排序运行得更快? 我认为它们的运行方式类似,因为每个位置的值都必须改变 . 插入排序的最坏情况是逆序,因此这意味着它是二次的,然后选择排序也已经是二次的 ... -
0 votesanswersviews
为什么我的mergesort实现比冒泡排序和插入排序慢?
我试图比较不同排序算法的时间复杂度(时间执行) . 我正在比较冒泡排序,插入排序,快速排序和融合排序(mergesort) . 我知道合并排序和快速排序比其他排序更快,但是当我尝试比较这些方法的执行时间时,合并排序总是比其他方法花费更多的时间 . 我尝试了1,000个元素到10,000个元素的列表 . 谁能告诉我为什么? 这是我的mergesort代码: def inserer(element, ... -
2 votesanswersviews
什么类型的输入区分插入排序和选择排序?
在什么样的测试用例中插入排序比选择排序更好?清楚地描述测试用例 . 为什么选择排序比该测试用例中的插入排序更差? 我回答了第一个问题: O(n2) . 当插入排序给出一个列表时,它接受当前元素并将其插入列表的适当位置,每次插入时调整列表 . 它类似于在纸牌游戏中安排卡片 . 第二个问题: 因为Selection Sort总是进行n(n-1)/ 2次比较,但在最坏的情况下,它只会进行n-1... -
0 votesanswersviews
具有给定反转次数的列表的冒泡排序和插入排序的复杂性
设列表的长度为n,反转次数为d . 为什么插入排序在O(n d)时间运行,为什么冒泡不排序? 当我考虑这个问题时,我正在考虑最糟糕的情况 . 由于反转的最坏情况是n(n-1)\ 2,因此气泡和插入排序都在同一时间运行 . 但后来我不知道如何回答这个问题,因为我发现它们是一样的 . 有人可以帮我弄这个吗? -
0 votesanswersviews
如何在时间和空间复杂度的限制下对偶数和奇数进行排序?(C / C)
鉴于 integer array 喜欢 int numbers[8]={1, 3, 5, 7, 8, 6, 4, 2}; 前阵列中的半边是奇数,其余(等量数)是偶数 . 奇数按升序排列,偶数部分按降序排列 . 排序后,数字的顺序不能改变 . 如何以时间复杂度 less 和空间复杂度 O(1) 交替对它们进行排序? 对于此示例,结果将是: {1,8,3,6,5,4,7,2} ; I can't u... -
-1 votesanswersviews
大O符号的计算机科学对数? [关闭]
我一直都有这个问题,并且从来没有能够将这两个概念联系起来,所以我正在寻找一些帮助来理解计算机科学中的对数关于Big-O表示法和算法时间复杂度 . 我将对数理解为能够回答问题的数学概念,"what number do I need to raise this base to exponentially to get X?" . 例如,log2(16)告诉我们需要将2增加到4才能得... -
1 votesanswersviews
恒定时间和有效恒定时间复杂度之间的差异
我理解“恒定时间复杂度O(1)”,但当我遇到有效的恒定时间复杂度这个术语时,我非常困惑 . 我从Scala厨师书中得到了关于有效恒定时间的句子 . 操作有效地持续时间,但这可能取决于某些假设,例如向量的最大长度或散列键的分布 . 但我认为上面的例子并不是有效的恒定时间,而是Amortize恒定时间 . 请你明确区分恒定时间和有效恒定时间 . 这将非常有帮助 . 谢谢!! -
1 votesanswersviews
矩阵时间复杂度分析中最长的增长路径
我正在研究下面的算法: Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or mo... -
5 votesanswersviews
std :: map get value - find vs handcrafted loop [关闭]
我有一个std :: map对象 map<string , Property*> _propertyMap ,其中 string 是属性的名称, Property* 包含属性值 . 我需要处理属性值并将它们转换为特定的数据格式 - 每个属性都有自己的格式,例如..如果映射初始化如下: _propertyMap["id"] = new Property(Prope... -
1 votesanswersviews
遍历由其边缘表示的树
我的树由其边和根节点表示 . 边列表是 undirected . char[][] edges =new char[][]{ new char[]{'D','B'}, new char[]{'A','C'}, new char[]{'B','A'} }; char root='A'; 树是 A B C D 如何在这棵树上进行深度优先遍历... -
1 votesanswersviews
广度优先搜索的时空复杂性
我只是想检查一下我对Russell和Norvig中给出的算法和计算的理解是否正确 . 我使用传教士和食人族作为测试时间和空间复杂性的问题 . 计算深度并不是什么大不了的事 . 我总是在深度11处找到解决方案 . 我无法解决的问题是分支因素 . Russell和Norvig第82页说: “探索集合中将有O(b ^(d-1)个)节点,边界中有O(b ^ d)个节点......” 我的程序在探索的集... -
-2 votesanswersviews
计算函数的空间复杂度和时间复杂度
作为课程作业的一部分,我需要计算程序的复杂性 . 我想计算下面程序的空间复杂度和时间复杂度 . 我如何计算它?如果有人可以详细解释它,对我来说真的很有帮助 . sub find_multi_string { my ($file, @strings) = @_; my $fh; open ($fh, "<$file"); #store th... -
0 votesanswersviews
时间复杂度与空间复杂性
我试图从短算法中理解时间和空间复杂性之间的差异 . 此代码采用列表/数组并返回发生奇数次的单个数字 . 在Python中: def foo(array_of_ints): hash_table = dict() for i in array_of_ints: hash_table[i] = hash_table.setdefault(i, 0) + 1 fo... -
2 votesanswersviews
“最大二叉树深度”的递归方法(Java)的时间复杂度是多少?
这个问题取自LeetCode的“Binary Tree of Binary Tree”: Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf ... -
0 votesanswersviews
用于确定 balancer 二叉树的蛮力的运行时复杂性
我有以下蛮力方法的代码来确定二叉树是否 balancer : public boolean IsBalanced(Node root) { if (root == null) return true; return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && IsBalanced(roo... -
1 votesanswersviews
迭代加深深度首先搜索比深度优先搜索更高的时间复杂度?
似乎迭代深化搜索应该具有比BFS更高的渐近时间复杂度,因为每次深度限制增加时,它必须从头开始搜索 . 但维基说不然,为什么? -
2 votesanswersviews
算法的最坏情况怎么会有不同的界限?
我一直试图弄清楚这一点 . 其他一些线程解决了这个问题,但我真的不明白答案 . 还有许多答案相互矛盾 . 我知道算法永远不会超过上限,永远不会比下限更快 . 但是,我不知道最佳案例时间存在上限,最坏情况时间存在下限 . This question really threw me in a loop.我无法绕过这个...给定的运行时间可以有不同的上限和下限? 例如,如果有人问:“显示大小为n的堆上... -
0 votesanswersviews
最糟糕的案例时间复杂性列表
我知道二进制搜索的最佳,平均和最差情况时间复杂度在Best O(1);平均O(log n);最糟糕的O(log n);用于数组实现 . 同样,我知道插入排序的最佳,平均和最差情况时间复杂度为Best O(n);平均O(n ^ 2);最差的O(n ^ 2);用于数组实现 . 但是,我如何解决二元搜索和插入单链表的时间复杂性;双重链表;和循环链表实现? -
-2 votesanswersviews
n-ary搜索的时间复杂度 .
我正在研究N元素中二元搜索,三元搜索和k元搜索的时间复杂度,并且已经提出了它各自的渐近更差的运行时间 . 但是,我开始想知道如果我将N个元素分成n个范围(或者n个n元素中的n元搜索)会发生什么 . 这是一个数组中的排序线性搜索,它会导致O(N)的运行时间?这有点令人困惑 . 请帮帮我! -
1 votesanswersviews
将元素插入此结构的摊销时间复杂度是多少?
假设您使用数组实现堆,并且每次数组已满,您将其复制到其大小的两倍的数组 . 将元素插入堆中的摊销时间复杂度(最坏的情况)是多少? 我认为我们有 T(n) = n * n (这是最坏情况下n个操作序列的总成本的上限),然后根据一个公式的摊销复杂度是 T(n) / n = n^n / n = n . 但我认为这是非常错误的,因为从直觉上可以清楚地知道我应该得到 log(n) 或更低......所以我... -
0 votesanswersviews
使用最坏情况,平均情况或摊销分析的公约?
我理解为算法执行复杂性分析的不同情况的机制,但是已经给出了几个场景,并且已经被问到我将针对每种情况使用哪种类型的分析 . 分析类型是“最坏情况”,“平均情况”,“摊销” . 当然要确保算法尽可能高效,我们总是选择使用“最坏情况”? 我意识到这是主观的,但使用每种分析方法肯定有优点吗? 这是我在最近的一次面试中给出的4种情景,除了关于飞行员的情况之外,我们无法决定其中的任何情况 . 一家公司发明了... -
0 votesanswersviews
二进制搜索的算法时间复杂度
我想弄清楚算法的时间复杂度是什么,我有二进制搜索算法,一般是O(log n),我知道 . 但我搜索两个常数,即x = 1和x = 2 ^ 31 - 1(整数的大小) . 我认为在最坏的情况下,我的时间复杂度是log2(2 ^ 31)= 31,所以在最坏的情况下二进制搜索需要31步 . 然而,二进制搜索中的每一步我都调用一个函数,它具有O(n)运行时(只有一个输入大小的循环) . 我的算法是否只... -
-3 votesanswersviews
二进制搜索字符串的复杂性
我有一个排序的字符串数组:例如:[“bar”,“foo”,“top”,“zebra”]我想搜索输入字是否存在于数组中 . 例如: search (String[] str, String word) { // binary search implemented + string comaparison. } 现在二进制搜索将考虑复杂度,即O(logn),其中n是数组的长度 . 所以这么... -
1 votesanswersviews
O(E)最短路径
有没有办法在O(E)中找到任意权重的图中从单个源到顶点的最短路径,但如果最短路径有7个或更少的边,则只需要担心它 . Bellman-Ford算法的最佳案例运行时间为O(E),这适用于此吗? -
0 votesanswersviews
Dijkstra的算法 - 为什么每次都提取具有最小优先级的顶点?
我正在学习Dijkstra的算法以找到最短路径 . 我注意到有一个优先级队列来帮助提取顶点集中具有最低优先级的顶点 . 如果我是 pick a vertex regardless of priority ,而不是优先级最低的算法,那么算法是否仍然有效? If yes, what about the time complexity? 来自维基百科的原始Dijkstra算法如下: function ... -
0 votesanswersviews
找到一个有效的算法来获得一条线
给定n个水平线段,其中每个线段的范围是x2 - x1,我应该应用什么算法来获得一条直线,它让我获得最大的 combined 范围(每个线段与一个线段相加会增加该线段的范围),就像发现一样钻一条线,以获得最大量的水(水代表具有X2-X1数量的区段)我完成了蛮力算法,令人沮丧 big O (n^4)