1回答
我相信我在某种程度上理解了合并排序，我试图理解合并排序的时间复杂性，但我发现很难完全理解它。因此，我们将递归地将合并调用到每个(即左、右子数组)，这将是log(n)，我理解这一点。但是合并排序的合并部分表示其复杂度为o(n)，使得整个时间复杂度为O(nlog(n))。但是我不太明白合并部分为什么是线性的，因为对于每个子数组调用，都会有len(sub_array)
浏览 4提问于2022-09-12得票数 -1
1回答
考虑到A是k数组的数组。每个内部数组都进行排序，并包含m个元素。给出了合并A中K排序数组的算法：K-arrays-merge(A) 2.我的第一个想法是，递归方法运行日志时间，在每一轮复制数组时，数组是O(m *
浏览 0提问于2018-03-15得票数 1
回答已采纳
1回答
合并K个排序数组/向量复杂度
、、、、
在研究合并k个排序的连续数组/向量的问题时，以及它与合并k个排序的链表的实现有何不同，我发现了两个相对简单的解决方案，用于合并k个连续数组，以及一个基于成对合并的很好的优化方法，该方法模拟了mergeSort我们创建一个输出vector<int>，并将其
浏览 2提问于2016-08-29得票数 3
回答已采纳
我听说heapq.merge函数是专门用来合并2个有序数组的？时间复杂度是O(n)吗？如果不是，它是什么?为什么？还有它的空间复杂性是什么。我正在解决用两个指针合并两个排序数组的问题，并且可以达到O(n)时间复杂度和O(n)空间复杂度。
浏览 51提问于2019-02-18得票数 5
要对大小为n的整数的基本数组进行排序，找出k个最小的元素，什么函数会导致O(nlogk)的时间复杂度？
例如，当查看合并排序时，它给出的时间复杂度为O(nlogn)。时间复杂性从何而来？
浏览 16提问于2021-05-29得票数 1
1回答
我应该做哪些更改来计算100000个输入的反转次数。return inv_count;{
j = mid; // j is the index for right subarray
k[k++] = arr[j+
浏览 0提问于2019-09-27得票数 0
2回答
使用二进制堆的多数组合并
、、、
给定k个排序的整数数组，每个数组包含未知的正数量的元素(不一定每个数组中的元素数目相同)，其中所有k个数组中的元素总数为n，给出了将k个数组合并为包含所有n个元素的单个排序数组的算法。该算法的最坏情况时间复杂度应为O(n∙log )。
浏览 2提问于2011-03-27得票数 4
3回答
合并大小为n的k个排序数组的下界
、、、、
正如标题所暗示的，我想知道合并大小为n的k个排序数组的下界的证明是什么？我知道这个界限是O(kn*logk)，但这是如何实现的呢？我尝试使用决策树对p个元素的数组进行排序，但我不知道如何实现此证明。
浏览 0提问于2017-10-10得票数 1
1回答
合并排序除以伪码的4次复杂度
、、、、
我需要为合并排序(除以4)编写伪代码，并计算出它的时间复杂度(显然它必须是Nlog(n)的时间复杂度)。= (n/4) m=(2n/4) z=(3n/4)
Return Merge4(Mergesort4(A[0..k-1]), Mergesort4(A[k..m-1]),Merge函数合并2个数组，并为已排序的元素创建一个新数组。(<em
浏览 1提问于2017-05-13得票数 0
回答已采纳
我对算法分析还比较陌生，并且正在修一门关于coursera的相关课程，我在那里学到了k路合并排序。2路合并排序的时间复杂度为n log2 n，3路合并排序的时间复杂度为n log3 n，4路合并排序的时间复杂度为n log4 n。但是，在k路的情况下，复杂度是nk^2，这是因为我们注意到了algo；(2n + 3n + 4n...kn)的
浏览 0提问于2014-05-15得票数 6
假设我们获得了k排序数组(每个大小为n)，那么在这种情况下，优先级堆的使用要比传统的合并(类似于合并排序中使用的合并)要好，反之亦然？优先级队列方法:在这种方法中，我们有一个最小的k堆(最初，来自每个数组的第一个元素被添加到堆中)。注意:它占用O(kn)空间，因为这是最终数组的大小，这在计算渐近空间复杂性时主导堆的大小。
传统的合并:在这种方法中，我们合并
浏览 3提问于2018-11-17得票数 4
1回答
问题：演示如何仅使用字符比较在O(n)时间内排序字符串(按字典顺序排列)。证明你的答案是正确的。我拥有的：
这看起来真的应该是基数排序。基排序的时间复杂度为O(k*(m+d))，其中k是包含在数组中的字符串中的最大字母数，d是“桶”的数目(假设您使用的是基排序和桶排序)，在这种情况下，我们知道我们将
浏览 3提问于2020-12-01得票数 1
回答已采纳
我想实现对合并排序的修改，其中长度为k的n/k个子列表使用插入排序进行排序，然后使用合并排序的标准合并机制进行合并。我想知道在rum时间复杂度方面，为了使合并排序的修改版本等于合并排序的原始版本，k必须等于多少。这是我自己的一个概念性练习。代码和/或解释是值得赞赏的。
浏览 4提问于2013-10-23得票数 0
3回答
在处理顺序数字之后，我试图将两个非序号数组排序为一个数组。我是否需要对数组进行单独排序，还是有更有效的方法？
如果我在输出下面运行的代码是4，16，2，11，19。应该是0,1,2,3,4.
浏览 3提问于2017-09-13得票数 0
回答已采纳
3回答
问题如下:有k个长度为n/k的排序列表(我们假设k除以n)。我需要找到一个算法，将这些列表合并为一个长度为n的列表，运行时间复杂度为O(k + nlogk)。我在考虑按对合并列表，然后再按对合并列表，依此类推，当我得到一个长度为n的排序列表时，我就停止了。
当我计算我的算法的时间复杂度时，我得到了O(nlogk)，它比
浏览 2提问于2016-07-14得票数 1
假设我有长度为L的K数组A1到AK。我想在内存中合并这些数组，而不需要占用太多的辅助空间，这样我就有了格式的最终输出，最小L元素出现在A1中，其次是L，最小元素出现在A2中，等等。基于最小优先级队列的算法为输出数组需要额外的L*K空间。L*K约为10亿美元
浏览 3提问于2019-11-29得票数 2
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
云直播活动推荐
腾讯云开发者
