考虑到排序算法的平均案例复杂度Omega(n*lg(n))的硬下界，什么时候/为什么您决定用快速排序来实现这个选择算法，而不是仅仅使用随机枢轴或数组中简单(n/2)的位置？
浏览 2提问于2015-04-29得票数 3
回答已采纳
我知道graham scan最坏的运行时间是O(nlogn)，但我不确定如何生成最坏的数据。据我所知，这发生在对点进行排序的步骤中，所以这是否意味着我应该为我使用的排序算法生成最坏情况的数据？
浏览 23提问于2021-02-21得票数 1
我试图确定以下算法的最佳情况和最坏情况，但由于我们的教授声称算法的最佳情况和最坏情况是“相同的”，所以我真的很困惑。，下面是我最初的想法：最坏情况：输入数
浏览 4提问于2022-02-08得票数 0
回答已采纳
3回答
精确输入大小和时间复杂度
、、、、
在谈到时间复杂性时，我们通常使用n作为输入，这并不是对实际输入大小的精确度量。我很难证明，当使用特定大小的输入时，一个算法仍然处于相同的复杂性类中。我如何证明顺序搜索或任何算法都是相同的
浏览 5提问于2011-05-18得票数 1
回答已采纳
4回答
用Kruskal算法可以在最坏的情况下找到O(E log*V)中的最小瓶颈生成树。这是因为每个最小生成树都是最小瓶颈生成树。
但我被课程的面试问题困住了。在最坏的情况下，如何在线性时间内找到最小瓶颈生成树。请注意，我们可以假设在最坏的情况下，我们可以在线性时间内计算n个键的中值。
浏览 23提问于2014-04-05得票数 5
回答已采纳
在“探索算法”一书中，作者说
在最坏的情况下，哈希表需要O(N)-linear时间--对于所有事情，这都是非常慢的。在最坏的情况下，我理解散列函数将映射相同插槽中的所有键，哈希表在该插槽处启动一个链接列表来存储所有项。所以搜索需要线性时间，因为你必须逐个扫描所有的项目。我不明白的是，对于insert和delete，哈希表需要线性时间</
浏览 0提问于2017-12-10得票数 3
回答已采纳
1回答
我想在未排序的列表中找到近似的中位数，我知道两个算法算法2-中位数
我不能在我的项目中使用quickselect，因为它在最坏的情况下需要O(n^2)。我听说过中位数，但我的同事建议它需要O(n)和一些常数factor.therefore，它的时间复杂度是Cn，常数因子is比快速选择大。我想知道与中位数相关的常数因子是什么?为
浏览 10提问于2014-02-18得票数 0
如果我们有一个线性算法(例如，查找一个数字是否存在于给定的数字数组中)，这是否意味着Omega(n) = n？步骤数为n。我能做的最紧的界限是c*n，c = 1。但据我所知，Omega还描述了最好的情况场景，在本例中是1，因为搜索的元素可以位于数组的第一个位置，并且只占一个步骤。所以，根据这个逻辑，Omega(n) = 1。
哪个变体是正确的，为什么？谢谢。
浏览 0提问于2018-07-06得票数 2
回答已采纳
我能构建一个算法FindStats(A，k)吗？我知道有一个算法QuickSelect(A，k) (确定性算法)，它在线性时间内返回k‘阶统计量，但在我的</em
浏览 5提问于2018-12-19得票数 1
2回答
有没有可能设计一种排序算法 它的运行时间在最坏的情况下是二次=> n^2 但在大多数情况下 (也就是说，超过一半的n大小输入) 运行时间将是线性的=> n ?？我在考虑基数排序，把最坏的情况弄得更糟。 但我不知道这是否可能。
浏览 14提问于2020-12-27得票数 2
回答已采纳
算法S对A中的每个奇数执行O(logn)-time计算。
由此，我了解到时间复杂度随着n的偶数或奇数而变化。换句话说，如果n是偶数，则S取O(n)时间，当n为奇数时，S取O(logn)。
这是一个简单的问题，采取最好的情况和最坏的情况两种增长率，并<
浏览 1提问于2015-02-17得票数 2
回答已采纳
3回答
算法的平均时间复杂度为O(n*log(n))，最坏情况复杂度为O(n^2)。
假设Hoare的快速排序算法的某些变体，什么样的输入会使快速排序算法表现出最坏的情况复杂性？请说明与具体的快速排序算法(如枢轴选择等)的实现细节有关的任何假设，或
浏览 3提问于2011-01-16得票数 8
1回答
大约两个月前，我做了一个练习，上面写着：
给出n (n>=4)不同的元素，设计了计算第4最小元的分而治之算法。在最坏的情况下，算法应该以线性时间运行。我在这个问题上非常困难，只能找到在最坏情况下运行的相关算法O(n*k)。经过几个星期的努力，我们在老师的帮助下，设法“解决”了这个问题。最后的算法<
浏览 3提问于2020-01-17得票数 0
回答已采纳
2回答
对于算法，最好/最坏情况的界限是如何联系的？最坏情况是否与上界同义，而最佳情况是否与下限同义？或者你至少可以从另一个中派生出一个？或者它们是完全没有关系的？
浏览 6提问于2015-06-22得票数 2
您正在管理一个软件项目，其中涉及建立一个计算机辅助的医疗外科仪器。手术刀的确切位置取决于许多不同的参数，通常至少25，有时更多。您的程序员开发了两种用于定位刀具的算法，并正在征求您对使用哪种算法的建议：
算法A的平均运行时间为n，最坏的运行时间为n^4，其中n是输入参数的数目。算法B
浏览 2提问于2015-06-15得票数 4
回答已采纳
我很困惑，我以为在最坏的情况下运行时间使用Big，而最好的是使用Ω？谁能解释一下吗？
(lg n)不是最好的情况吗？(nlg n)是最坏的情况吗？还是我误会了什么？在大小为n的堆上，最大Heapify最坏的运行时间是Ω(lg n)。(提示:对于有n个节点的堆，给出节点值，使Max-Heapify在从根到叶<em
浏览 4提问于2013-03-14得票数 10
回答已采纳
2回答
我正在编写用于选择排序和插入排序的实现。然后用一个自动生成的阵列对它们进行测试，并在MAC OS下用Posix MAC OS以u秒的精度评估所需时间。但是在大多数情况下，在总65525和从-65525和+65525输入数组的范围内，插入排序要比选择排序快得多，大约有一半的时间表示。record:20092583 Min=(-65524)，index=(89660)；Max=(62235)，index=(23486)
浏览 3提问于2015-11-17得票数 1
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
腾讯会议
云直播
对象存储活动推荐
腾讯云开发者
