1回答
如何证明并行算法的上下界？
、、、、
假设有一个Fibonacci算法：我们被要求证明这个算法的上界/下界。更新功(N)= W(n - 1) + W(n - 2) +Θ(1)Work(n) = [W(n - 1) + W(n - 2) + Θ(1
浏览 20提问于2018-01-08得票数 2
1回答
堆排序的时间复杂度
、、、、
我到处读到堆排序的时间复杂性在最坏的情况下是O(nlog(n))。但是，我们在任何地方都看到，在O(nlog(n))中构建堆是一种常见的误解。相反，您可以在O(n)中创建一个堆。因此，考虑到可以在O(n)中创建堆，请看下面的排序算法，并告诉我分析其时间复杂性的错误之处。
总之，复杂性是O
浏览 0提问于2019-06-24得票数 0
有没有公式可以告诉我们map reduce算法的并行效率？(换句话说，我如何从数学上证明MR算法A比MR算法B更好)
我在谷歌上搜索了一下，但我可以在上找到并行算法的加速和效率的定义，但如果有人能展示这些公式如何应用于MR算法，那就太好了
浏览 0提问于2013-04-19得票数 0
回答已采纳
1回答
有什么问题是我们知道的下界吗？我的动机是:虽然我们不知道如何证明单向函数的存在，但也许我们不需要它来实现求函数和反转函数之间的可证明多项式分离。即使是\Omeg
浏览 0提问于2020-11-21得票数 2
回答已采纳
1回答
图的哈密顿性的FLS零知识协议如下。验证器选择一个随机位b并将其发送给发送方。如果b= 0，则prover对图的所有边进行分解，验证器验证它是否为循环图。
如果b= 1，则证明器计算G的hamiltonian圈与循环图C之间的等电点。然后分解C中所有不存在于G的同构中的边。该协议在许多地方被证明是
浏览 0提问于2019-08-07得票数 0
回答已采纳
3回答
壳体分类分析
、、、
我正在读一本关于算法的书，书中提到了对shell排序算法的分析，如下所示：，为什么作者提到坏的情况来检查下界？我教过要达到下限，我们
浏览 6提问于2011-09-09得票数 2
我已经证明了如果f(n)是Θ(h(n))且g(n) = O(h(n))，则f(n) + g(n)是O(h(n))，但现在当我试图证明/反证f(n) + g(n)也是Ω(h(n) )时，我遇到了一个问题下面是我的方法。从给定的， 存在b，c>0使得b.h(n) =< f(n) <= c(h(n))和存在a>0使得g(n) <= a.h(n) 我通过添加上述两个不等式证明了O(h(n))，但是为了正式地证明/反证下界，我被卡
浏览 13提问于2019-04-28得票数 0
如果你能为我提供一些关于以下问题的参考，那将是非常有帮助的：我知道k=1有很多例子，例如最接近的对/排序。
浏览 0提问于2011-02-08得票数 1
3回答
合并大小为n的k个排序数组的下界
、、、、
正如标题所暗示的，我想知道合并大小为n的k个排序数组的下界的证明是什么？我知道这个界限是O(kn*logk)，但这是如何实现的呢？我尝试使用决策树对p个元素的数组进行排序，但我不知道如何实现此证明。
浏览 0提问于2017-10-10得票数 1
根据主定理的第二种情况，我们会得到Θ(nlog(n))的时间复杂度，同时，使用替换方法(+归纳法)，我们也可以得到它在O(nlog(n))中，即我们可以证明c>1和n>1的T(N) <= cnlog(n为什么这是不同的，这有关系吗？谢谢!
浏览 22提问于2021-05-12得票数 0
回答已采纳
2回答
事实证明，基于比较的排序具有复杂性T(n)=nlogn。那么，如果我们有正整数数组(不是特定的整数，因此不能应用counting或radix排序)，那么如何确定从Sort到SortPositiveNumbers (例如)的适当约简，以证明存在多项式和正确的变换，而SortPositiveNumbers也有nlogn的下界？
浏览 0提问于2016-02-11得票数 2
回答已采纳
为此，我认为要正确地解决它，我需要证明sigma(logn)是它的下界。我知道我的书中的所有比较都在O(nlogn)中运行，但我不确定如何将其形成一个具体的答案。
浏览 1提问于2011-10-14得票数 0
回答已采纳
1回答
参考维基百科的这篇文章：，重点是构建排序网络的段落。
请您解释一下(表中) Size, upper bound和Size, lower bound是什么吗？我希望lower bound引用正确排序n个数字的输入所需的最小连接(我是正确的吗？)如果是这样的话，为什么要费心使用upper bound呢？理论上，我们可以使用一些比upper bound更大的连接，那么如何建立它呢？我也读过链接的报纸(参考文献)。11)但我仍然感到困惑。
浏览 2提问于2016-09-02得票数 2
回答已采纳
6回答
S是一种支持时间Find_Smallest_Item T(n)中插入(x，S)、删除(x，S)和<= (S)的数据结构。证明了T(n)的一个下界，如Ω(logn)。到目前为止我的想法如下：但在这里，我们正在
浏览 0提问于2011-10-04得票数 5
回答已采纳
作为密码学的新手，我正在编写“现代密码学导论”一书中的练习2.12。📷
但问题是:我在\lvert\Pr[M=m\mid C=c]-\Pr[M=m]\rvert\leq\epsilon的<
浏览 0提问于2019-09-30得票数 2
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
云直播活动推荐
腾讯云开发者
