-
1 votesanswersviews
使用inorder后继方法打印BST的时间复杂度
我有一种方法可以在二进制搜索树（BST）中查找下一个inorder后继 . “inorderSuccessor”方法将BST的任何节点作为输入并输出下一个inorder后继 . 方法和树类定义如下： class BSTInorderSuccessor{ public static Node inorderSuccessor(Node node) { if (node.right !=... -
5 votesanswersviews
std :: map get value - find vs handcrafted loop [关闭]
我有一个std :: map对象 map<string , Property*> _propertyMap ，其中 string 是属性的名称， Property* 包含属性值 . 我需要处理属性值并将它们转换为特定的数据格式 - 每个属性都有自己的格式，例如..如果映射初始化如下： _propertyMap["id"] = new Property(Prope... -
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... -
28 votesanswersviews
合并排序的最坏情况何时会发生？
我知道mergesort的最坏情况是O（nlogn），与普通情况相同 . 但是，如果数据是升序或降序，则会导致最小比较次数，因此mergesort变得比随机数据快 . 所以我的问题是：什么样的输入数据产生最大数量的比较，导致mergesort变慢？ this问题的答案是： 对于某些排序算法（例如快速排序），元素的初始顺序可能会影响要完成的操作数 . 然而，它不会对mergesort进行任何更改，... -
-1 votesanswersviews
大O符号的计算机科学对数？ [关闭]
我一直都有这个问题，并且从来没有能够将这两个概念联系起来，所以我正在寻找一些帮助来理解计算机科学中的对数关于Big-O表示法和算法时间复杂度 . 我将对数理解为能够回答问题的数学概念，"what number do I need to raise this base to exponentially to get X?" . 例如，log2（16）告诉我们需要将2增加到4才能得... -
0 votesanswersviews
使用随机元素进行二进制搜索
我知道二进制搜索具有 O(logn) 的时间复杂度来搜索排序数组中的元素 . 但是，让我们说如果不选择中间元素，我们选择一个随机元素，它将如何影响时间复杂度 . 它仍然是 O(logn) 还是其他的东西？ 例如：一个大小为18的数组中的传统二进制搜索将会像18 - > 9 - > 4那样下降... 我修改的二进制搜索ping一个随机元素，并决定根据值删除右边部分或左边部分 . -
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是数组的长度 . 所以这么... -
2 votesanswersviews
是否存在最差情况时间复杂度为n ^ 3的排序算法？
我熟悉其他排序算法，我在多项式时间听到的最糟糕的是插入排序或冒泡排序 . 排除真正可怕的bogosort和类似的那些，是否有任何排序算法的多项式时间复杂度比n ^ 2更差？ -
9 votesanswersviews
这种愚蠢的排序最糟糕的时间复杂性？
代码如下： for (int i = 1; i < N; i++) { if (a[i] < a[i-1]) { swap(i, i-1); i = 0; } } 在尝试了一些事情后，我认为最坏的情况是输入数组是降序 . 然后看起来比较将是最大的，因此我们将只考虑比较 . 然后它似乎是总和的总和，即...... {1 2 3 ...（n... -
1 votesanswersviews
堆排序时间复杂性深刻理解
当我在大学学习数据结构课程时，我学到了以下公理： 在最坏的情况下将新数字插入堆需要 O(logn) （取决于作为叶插入时它到达树中的高度） 使用 n 节点构建一堆 n 节点，从空堆开始，使用摊销分析求和为 O(n) 时间 在最坏情况下删除最小值需要 O(logn) 时间（取决于新顶节点在与最后一个叶子交换后达到的低点） 逐个删除所有最小值，直到堆为空，需要 O(nlogn) 时间复... -
1 votesanswersviews
最坏的情况下时间复杂
未排序的n个数字列表，在具有最小差异的列表中找到任意两个数字 . 如果我必须为此编写算法，最坏的情况时间 O(nlogn) . 以下算法可以工作： 使用合并排序的排序列表 遍历整个列表一次，找出连续数字之间的差异 . 返回最小差异的数字 . 这种算法的时间复杂度是： O(nlogn + n) 我可以说 O(nlogn) ？ -
1 votesanswersviews
二进制搜索的最坏情况是什么？
元素应该放在数组中的哪个位置，以便二进制搜索算法的运行时间为O（log n）？ -
0 votesanswersviews
为什么二进制搜索算法中的赋值不会增加时间复杂度？
对于插入排序更糟糕的情况，其中存在n个递减元素的数组 . comparing 所有元素从左到右花费的总时间是： 1 2 ...（n - 2）（n - 1） 在计算时间复杂度时也考虑了这些元素，这也是： 1 2 ...（n - 2）（n - 1） 最终，我们到达O（n ^ 2） . 采取另一种算法，如二元搜索; the act of finding a midpoint ，然后... -
0 votesanswersviews
找到有向图的最短路径
对于 (u, v) ∈ E ，有一个有向图 G = [V ; E] ，边权重为 w(u, v) . 假设 {d[v], π[v]}; v ∈ V 和声明的值 这些是最短路径的长度和前一个节点的长度 它为 v ∈ V ，我怎么能验证这个语句是真还是假，不能从头开始解决整个最短路径问题？这是我遇到的一个问题，我头脑中的想法不多 . -
4 votesanswersviews
带有彩色边缘的图形：最短路径，最多k个颜色变化？
我有一个带有彩色加权边的有向图 . 有2种颜色 . 每个边缘只能有1种颜色 . 我想找到颜色变化有限的最短路径 . 从一个顶点可以出现最多2个边缘，其中有2种不同的颜色，2个边缘有2种不同的颜色 . 例如，在此图中： 最短路径最多3个颜色变化 9 最大 0 颜色变化最短路径是 6+1+4=11 等 . 我的解决方案是递归访问所有可能的路径并交换，如果递归找到一个更好的，使这个问题呈指数级 . 是... -
0 votesanswersviews
二叉搜索树的时间效率
为了插入二叉搜索树的时间效率， 我知道插入的最佳/平均情况是O（log n），其中最坏的情况是O（N） . 我想知道的是，除了实施AVL（ balancer BST）之外，是否有任何方法可以确保我们在插入时始终具有最佳/平均情况？ 谢谢！ -
3 votesanswersviews
Apache Spark RDD sortByKey算法和时间复杂度
Apache Spark RDD sortByKey的Big-O时间复杂度是多少？ 我正在尝试根据特定订单将行号分配给RDD . 假设我有一个{K，V}对RDD，我希望按键执行订单 myRDD.sortByKey(true).zipWithIndex 这个操作的时间复杂度是多少？ 而且幕后发生了什么？泡泡排序？我希望不是！我的数据集非常大并且跨分区运行，所以我很好奇sortByKey函数是否是最... -
9 votesanswersviews
深度优先搜索的时间/空间复杂性
我查看了其他各种StackOverflow答案，它们都与我的讲师在幻灯片中写的不同 . 深度优先搜索的时间复杂度为O（b ^ m），其中b是搜索树的最大分支因子，m是状态空间的最大深度 . 如果m比d大得多，但是如果搜索树是“浓密的”，则可能比广度优先搜索快得多 . 他继续说.. 空间复杂度为O（bm），即动作序列长度的空间线性！只需存储从根节点到叶节点的单个路径，以及路径上每个节点的剩余未...