分析合并排序输入加倍时的时间复杂度

文章/答案/技术大牛

发布

3回答

仅使用运行时数据查找大O时间复杂度函数

java、algorithm、sorting、time-complexity、big-o

在我为算法类准备的一个项目中，我们必须运行5种未知类型的不同排序方法，并使用加倍方法收集每个方法的运行时间数据。然后，我们必须使用运行时间的比率来计算时间复杂度的函数。使用的排序方法有选择排序、插入排序、合并排序和快速排序(随机和非随机排序)。我们必须通过实

浏览 0提问于2018-10-03得票数 2

回答已采纳

1回答

time-complexity、complexity-theory

我试图从理论上理解，当传递给合并排序的输入大小加倍时，需要多长时间。我正在读一本课本，上面写着：由于合并排序(对于大N)的运行时间是O(N log_2 N)，我们应该考虑比率r= N^{ 1.1 } log_2(N^{1.1})/(N log_2(N))。这简化为1.1 N^{0.1}，约为3.5 我想问他们是如何计算出，当输入大小加倍时</e

浏览 11提问于2020-01-30得票数 0

2回答

程序运行时近似公式

c、function、time、execution

我有一个C程序，它对以下输入数在以下时间内执行：100 0.001s 有什么想法吗？1)我用CPU时间(user+sys)来测量这个值。2)我的程序使用快速排序 2)程序的渐近运行时分析/复杂度为O(

浏览 2提问于2013-11-14得票数 3

2回答

为什么k路合并排序O(nk^2)的时间复杂性？

algorithms、sorting

我对算法分析还比较陌生，并且正在修一门关于coursera的相关课程，我在那里学到了k路合并排序。2路合并排序的时间复杂度为n log2 n，3路合并排序的时间复杂度为n log3 n，4路合并排序的时间复杂度为n log4 n。但是，在k路的</e

浏览 0提问于2014-05-15得票数 6

1回答

排序算法的内存速度权衡

performance、algorithm、sorting、memory、complexity-theory

只考虑冒泡排序和合并排序。对于冒泡排序，时间复杂度为O(n)到最坏情况为O(n^2)，空间复杂度为O(1)。对于合并排序，时间复杂度为O(nlogn)，空间复杂度为O(n)。如果输入的大小小于1000，你会选择哪种类型?为什么？如果超过1000个呢？这是我的面试问题。我只想知道你们会怎么回答。

浏览 1提问于2013-03-12得票数 1

回答已采纳

1回答

对包含大量数据的文件进行排序

time-complexity、array-algorithms

考虑到一个包含N字的文件，每个line.The文件一个字太大，所以不能在内存中一次读取整个字。排序每个块的时间= xlogx (假设我使用快速排序)因此总时间复杂度=

浏览 2提问于2011-07-03得票数 1

3回答

迭代合并排序的运行时间和不变量是多少？

algorithm、sorting、mergesort

我想知道，在迭代和递归合并排序的运行时间和不变量之间是否存在差异。如何更改合并排序(迭代或递归版本)，使最佳情况与插入排序相同？

浏览 5提问于2020-08-20得票数 2

回答已采纳

2回答

真的对时间复杂性感到困惑

sorting、time、complexity-theory

我知道如何计算每种算法的bigO，以及它是如何工作的。例如，在链表中查找特定数字将是O(N)，因为您可能需要从头到尾检查链表中的每个输入。然而，关于时间，bigO到底意味着什么呢？为什么合并排序可以比插入排序运行得更快，尽管插入排序具有更快的“时间复杂度”？请给我你的意见，以便我能理解。非常喜欢THankyou。

浏览 2提问于2015-04-01得票数 0

1回答

递归如何降低合并排序中的时间复杂度

time-complexity、mergesort

根据我的理解，时间复杂度是通过计算运算数随输入大小的增加而得出的。根据视频讲座，为合并排序划分数组的时间复杂性是O(log n)。但在这里，他不是指计算时间复杂度的操作数，

浏览 5提问于2021-08-04得票数 0

1回答

一种合并排序算法的递推关系

algorithm、data-structures、mergesort、recurrence

问题是：给出了不平衡合并排序算法在最坏情况下时间复杂度的递推关系。UNBA

浏览 4提问于2015-05-02得票数 2

回答已采纳

2回答

关于尝试排序和基排序的效率

big-o、time-complexity、trie、radix-sort

基排序的时间复杂度为O(kn)，其中n是要排序的键数，k是键的长度。类似地，trie中插入、删除和查找操作的时间复杂度为O(k)。但是，假设所有元素都是不同的，难道不是k>=log(n)吗？如果是这样，则意味着基排序的渐近时间复杂度为O(nlogn)，等于快速排序，而trie操作的<em

浏览 3提问于2011-07-31得票数 3

回答已采纳

1回答

很难理解用于合并K个排序列表的递归序列

python、recursion、merge、linked-list

我一直在尝试理解这个leetcode问题的递归顺序，我也找到了一个解决方案。我理解merge函数，但我不理解mergeKLists函数上的递归。如果能帮上忙，我们将不胜感激。请尽可能描述性地向我展示导致最终合并链表的调用和返回。*我理解合并函数，所以不需要解释它。

浏览 12提问于2019-12-27得票数 0

回答已采纳

3回答

如何在合并排序和插入排序之间进行选择？

c、sorting、mergesort、insertion-sort

我需要实现最快的排序算法来对使用stdin创建的链表进行排序。我知道合并排序的时间复杂度是O(n logn)，插入排序的时间复杂度是O(n^2) (n是链表中元素的数量)。但是列表是由标准输入创建的，那么对未排序的列表使用merge-sort更有效，还是通过插入-排

浏览 0提问于2019-09-10得票数 2

1回答

改进的归并排序算法

algorithm、mergesort

描述一种改进的合并排序算法，在该算法中，给定的序列被分割成大小相等的大约三分之一的三个子序列。渐进地分析算法的时间复杂度。如何解决这个问题？

浏览 1提问于2012-11-12得票数 0

2回答

应用于链表合并排序的分步时间复杂度

algorithm、linked-list、mergesort

我一直在查看合并排序在链接列表中的应用。我看过的一些文章指出，合并排序是排序链接列表的最佳算法。分而治之策略中的征服部分是有意义的，当您最终节省所需内存(与数组相比)时，合并两个排序链接列表是有意义的。但是，我不明白的是算法中分步的时间复杂度。我对分步做了一些分析</

浏览 3提问于2021-05-20得票数 1

回答已采纳

3回答

合并排序时间复杂度与我的算法。大O

big-o、analysis、asymptotic-complexity

这是我正在尝试分析的一个算法(见下文)。我不明白为什么当合并排序具有O(n logn)时，这会有O(n)时间复杂度，它们似乎都在做同样的事情。那么两者都有相同的j时间复杂度，如果你让j作为行，那么2^j X c(n/2^j) = cn，它们的运行时间都是log n，其中n是元素的数量。

浏览 1提问于2012-08-09得票数 1

回答已采纳

7回答

什么是算法的摊销分析？

algorithm、analysis、amortized-analysis

它与渐近分析有什么不同？你什么时候使用它，为什么？那么，有没有人能帮我简化一下？

浏览 95提问于2012-06-19得票数 88

3回答

为什么递归合并排序优先于迭代合并排序，即使后者具有辅助空间复杂性？

algorithm、sorting、recursion、mergesort

在研究合并排序算法时，我很想知道这个排序算法是否可以进一步优化。发现合并排序算法存在迭代版本，具有相同的时间复杂度，但O(1)空间复杂度更好。从性能上看，迭代方法总是比递归方法更好。

浏览 0提问于2021-03-18得票数 1

回答已采纳

7回答

合并排序时间和空间复杂度

algorithm、time-complexity、mergesort、space-complexity

让我们以合并排序的实现为例if (r <= l) return;mergesort(a, l, m); ------------(1)merge(a, l, m, r); 这种合并排序的时间复杂度是O(( b)这种合并<

浏览 0提问于2012-04-26得票数 46

回答已采纳

1回答

在考虑时间复杂性时，Theta(n)和T(n)有什么区别？

algorithm、time-complexity、mergesort

教授正在讨论合并排序的时间复杂性，他将整个过程分为三个步骤。我不明白第二步，为什么他把它描述为2T(n/ 2

浏览 4提问于2015-09-05得票数 0

回答已采纳

点击加载更多

仅使用运行时数据查找大O时间复杂度函数