我试图将我的算法运行时降到O(n + klogk)，但我似乎无法做到这一点。我正在使用最小堆获得O(n + nlogk)。基本算法如下：
对于每个元素，在kth元素(arrk到arrn-1)之后，将其与MH的根进行比较。O((n-k</e
浏览 0提问于2018-02-20得票数 1
回答已采纳
在寻找数组A中k个最小或最大元素的练习中，有一个解决方案可以产生O(k + (n-k)Logk + kLogk)运行时间。然而，我的朋友告诉我这个表达式等于O(n + klogk)。我不确定他是对是错，有人能帮我算一下这个数学题吗？
浏览 5提问于2018-02-21得票数 0
回答已采纳
问题是:数组是k排序的，如果所有元素最多按k个位置错位(相对于真正的排序顺序)。在时间O(n日志k)中对k排序数组进行排序。我的解决方案是: 1.创建大小为n的新数组(这是O(1)) 2.创建大小为k的最小堆并填充数组的前k元素(这是O(k))。3.逐个从min堆中移除min
浏览 0提问于2018-02-26得票数 0
回答已采纳
2回答
我们有一个n节点二进制堆，其中包含n不同的项(最小的根项)。对于k<=n，找到一个O(klogk)时间算法来从堆中选择kth最小元素。
O(klogn)很明显，但是想不出一个O(klogk)。
浏览 1提问于2011-10-05得票数 34
回答已采纳
2回答
算法的下限是多少？
、、、、
让一个算法得到一个大小为n的未排序数组。让一个数字k<=n。该算法从1到k(升序)输出k-最小数.该算法的下界是什么(每k个)？Omega(n)
#1，#2都是正确的。现
浏览 1提问于2015-02-16得票数 1
1回答
给定数组(未排序)和很少的范围查询。对于每个查询，我需要在给定范围内找到唯一的数字数。这是我想出的天真的方法。#include<cstdio>using namespace std;
{ int a[n+1]; a[0]=0;
浏览 7提问于2015-01-17得票数 1
1回答
数组中的Kth和
、、、、
我有一个有n个元素的数组，我需要计算两个元素对的n*n和(arrayi+arrayj).All和按升序排列，我需要找到Kth和。例如：所有总和：{(3+3)，(3+4)，(4+3)，(3+5)，(5+3)，(4+4)，(4+5)，(5+4)，(5+5)}我需要找到Kth和的值(在这种情况下，第6和是4+4，我将返回8)；
这是我的解决方案；它不是
浏览 4提问于2015-03-31得票数 1
1回答
考虑到A是k数组的数组。每个内部数组都进行排序，并包含m个元素。two sorted arrays with time complexity of O(n)
为什么这个算法的时间复杂度是O(m*klogk)？我的第一个想法是，递归方法运行日志时间，在每一轮复制数组时，数组是O(m * k)，合并排序是O( My log (My))，其中1 <= i <
浏览 0提问于2018-03-15得票数 1
回答已采纳
现在，我正在循环我的整个字典五次，并保持最高值后，每次迭代和删除条目。但这似乎是一种非常讨厌的方式来做我想做的事。基本上，我想得到我的字典的前五大价值，并返回键，有更好的方法来做这个，而不是重复它五次吗？
浏览 0提问于2014-02-25得票数 1
回答已采纳
问题是：
不过，我的问题是，我们能不能比nklogk少排序，这意味着，运行时是o(nklogk)。于是我在网上搜索并找到了这样的答案：
它声称将
浏览 5提问于2022-05-22得票数 0
1回答
以下是Java中问题的示例解决方案。
时间：O((n-k)(k * logk)) == O(nklogk)
空格(辅助)：O(<
浏览 1提问于2017-04-15得票数 2
回答已采纳
我们如何在O(k log k+ n)时间内将k个新元素插入到大小为n的排序列表中？
我猜klogk可以通过首先合并k个元素，然后将它们插入到大小为n的列表中来实现。但我遗漏了(+n)部分。
浏览 47提问于2018-12-12得票数 2
回答已采纳
2回答
我一直在为类实现选择排序问题，其中一个任务是使用最小堆在数组中找到kth最小元素。我知道程序是：
bool Example::min_heap_select(long k, long & kth_smallest) const {
浏览 3提问于2011-04-10得票数 5
回答已采纳
我不能回答一个问题，你能帮我吗？For i=1 to i=n/2, if A[i]<=A[2i] and A[i]<=A[2i+1] A is called as a "bst"
在一个有n个元素的bst中寻找kth最小元素的时间复杂度是多少
浏览 0提问于2015-06-14得票数 3
1回答
考虑到一个包含N字的文件，每个line.The文件一个字太大，所以不能在内存中一次读取整个字。
分析总的时间复杂度。我该怎么做呢？合并k块的时间= klogk (是吗？？)
浏览 2提问于2011-07-03得票数 1
1回答
一家家具店正在打折:以更贵的价格购买两件物品。约翰刚搬到一个新房子，冲进商店，选择了2k家具: f1，f2，…，f2k−1，f2k。价格分别为p1、p2、.、p2k−1、p2k。帮助约翰安排家具成对，这样2k项目的总成本是最低的。提出了一种在O(klogk)中运行的算法，证明了算法的正确性和运行时间。好的，听起
浏览 1提问于2014-11-09得票数 1
回答已采纳
c_set ={‘a’，‘b’，‘c’，‘g’}c_set覆盖了w_set，当w_set中的每一个w都被c_set中的某个c所覆盖。给定c_set和w_set，w_set是否在c_set的覆盖范围内？如果我们使用26位(每个字符1位)来表示w_set中<em
浏览 1提问于2013-10-15得票数 0
能不能在一组n个点中找到比快的最近点的k对
我知道我可以在O(nlogn)中计算最近的对点，但是使用该算法，并不是所有的距离都是计算出来的，所以我不能返回顶点k最近的点对()。如果使用"Brute“方法计算点的所有边的距离，这个问题很简单，但是这具有[n * (n-1)]/2的复杂性，我希望找到更有效
浏览 4提问于2019-03-04得票数 0
1回答
我想证明为什么在O( n )中找到n个大小的数组的最长的非连续的非递减子序列。 in NlogN.假设这可能比O(nlogn)更快，为了简单起见，O(n)，但这适用于比O(nlogn)更好的东西
我们可以将两个排序数组合并为<e
浏览 6提问于2020-07-06得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
腾讯会议
云直播
对象存储活动推荐
腾讯云开发者
