1回答
我知道，对于一些问题，不管你用什么算法来解决，总有一个最小的时间来解决这个问题。我知道BigO捕获了最坏的情况(所需的最大时间)，但是如何才能找到n的函数所需的最小时间呢？我们能找到排序n个整数所需的最小时间吗?或者也许可以找到n个整数的最小值？
浏览 1提问于2015-10-03得票数 3
回答已采纳
1回答
密切相关的排序算法，基排序和桶排序是自适应的吗？
我知道，如果要排序的数据是预先排序的，并且该算法花费最少的时间，那么排序算法就是自适应的。
然而，我无法断定基和桶排序算法是否是自适应的。
浏览 5提问于2020-08-21得票数 0
回答已采纳
2回答
我正在阅读排序方法，包括冒泡排序、选择排序、合并排序、堆排序、桶排序等。它们还包含时间复杂性，帮助我们知道哪种排序是有效的。所以我有个基本问题。如果我们包含的数据比我们将如何选择排序。时间复杂度是决定排序方法的参数之一。但是，我们是否有另一个参数来选择排序方法？
只是为了更好的理解而找出分类。
查询堆排序：
我们在哪里使用堆排序？
堆排序有什么更大的优势(除了时间复杂度O(n log ))？
堆排序的缺点是什么？
堆的构建时间是多少？(我听说了O(n)，但我不确定。)
任何必须使用堆排序或堆排序的场景都是更好的选择(除了优先级队列)？
在对数据应用堆排序之前，我们将查看
浏览 1提问于2012-03-21得票数 12
回答已采纳
1回答
我已经在Java中实现了一个基于堆的优先级队列，但是我现在面临的挑战是实现一个高效的Iterator，它具有一定的遍历顺序(增加或减少)。在O(n)的常辅助空间和时间复杂度上是否有这样的算法？O(nlogn)非常琐碎。此外，在O(n)空间算法中，绝对没有任何细微之处。如果可以的话请帮忙。
浏览 2提问于2022-04-14得票数 0
回答已采纳
2回答
最近我一直在学习算法设计，它涉及到在哪里获得增长的顺序(如果我错了)。我已经看到从插入排序到运行时间，这是为了计算算法，也许这是最坏的情况。问题是我不能理解如何找到n。例如：
print "Hello"
for i = 0 to n:
print i * 1
print "end of program"
所以，如果我想要计算运行时间，我应该如何得到n并计算T(n)。问题是我相信我不理解基本原理。我用谷歌搜索了一下，没有什么能让我满意，而且我也不明白。
谢谢。
浏览 0提问于2017-02-28得票数 0
我试图了解是否有任何替代蛮力算法(或轻微的改进/最坏的性能比幼稚的蛮力算法)仍然将导致O(N^2)的时间复杂性和O(1)辅助空间。
这是我的蛮力伪码：
procedure distinct(Input: array)
for i=0 to i < length of array
for j=i+1 to j < length of array
if array[i] ==
浏览 1提问于2016-03-07得票数 1
回答已采纳
3回答
有没有平均时间复杂度为log(N)的排序算法？
示例8,2,7,5,0,1排序时间复杂度为log(n)的给定数组
浏览 2提问于2021-05-26得票数 0
1回答
Kruskal的算法如下：
MST-KRUSKAL(G,w)
1. A={}
2. for each vertex v∈ G.V
3. MAKE-SET(v)
4. sort the edges of G.E into nondecreasing order by weight w
5. for each edge (u,v) ∈ G.E, taken in nondecreasing order by weight w
6. if FIND-SET(u)!=FIND-SET(v)
7. A=A U {(u,v)}
8. Union
浏览 4提问于2015-04-10得票数 8
回答已采纳
2回答
我不知道为什么下面的算法的运行时间是O(nlogn)。有谁能帮帮我吗？
public static boolean unique2(int[] data) {
int n= data.length;
int[] temp= Arrays.copyOf(data,n);
Arrays.sort(temp);
for (int j=0; j<n-1;j++)
if (temp[j]==temp[j+1])
return false;
return true;
}
浏览 2提问于2021-01-03得票数 2
2回答
算法A对存储n个元素的数组执行时间复杂度为O(log )的运算。
算法B从数组中选择log个元素，并对每个元素执行O(n)计算。
由于d(n) = O(f(n))和e(n) = O(g(n))，那么d(n)*e(n) = O(f(n)*g(n))，这是否意味着算法A和B的时间复杂度都是O( n )？
浏览 0提问于2018-11-11得票数 0
我在互联网上到处找过，找不到这样的wc时间复杂度排序算法.
我相信这不是Bogo ，因为wc不是无穷大的
浏览 2提问于2020-12-09得票数 1
/*
Returns true is the two strings are permutations of each other.
Time Complexity; O(nlog n) -> because of the java utils array sort
Space Complexity; O(1)
*/
public boolean isPermutationOptimized(String one, String two) {
if (one.length() != two.length()) {
return
浏览 17提问于2021-10-05得票数 0
回答已采纳
1回答
中位快速排序中值的最坏情况时间复杂度是多少(枢轴是由需要O(n)时间查找的中间值的中位数决定的)？
浏览 1提问于2014-11-22得票数 0
回答已采纳
这个问题已经出现在我的算法课上了。我的想法是：
我认为答案是否定的，具有O(n)的最坏时间复杂度的算法并不总是比O(n^2)的最坏时间复杂度的算法更快。
例如，假设我们有总时间函数S(n) = 99999999n和T(n) = n^2，那么很明显，S(n) = O(n)和T(n) = O(n^2)，但对于n< 99999999，T(n)比S(n)更快。
这样的推理有效吗？我有点怀疑，虽然这是一个反例，但它可能是错误想法的反例。
非常感谢！
浏览 5提问于2016-06-15得票数 3
回答已采纳
2回答
渐近分析问题
、、、
我在geeksforgeeks.org上发现了几个我似乎无法理解的问题(#1和#3)。我希望有人能帮我弄清楚答案：
澄清true/valid或false
1. QuickSort的时间复杂度为Θ(n^2)
我的回答是正确的，但它是错误的，为什么？如果快速排序的时间复杂度为O(n^2)，并且我们知道快速排序(g(N))={ f(n)，其中c1*g(n) <= f(N) <=c2*g(n)和n >= n0}，那么这不是证明它是真的吗，因为c2*g(n)作为上界可以等于f(n)？
2. QuickSort的时间复杂度为O(n^2) -真
3.所有计算机算法的时间复杂度可以写成Ω(1
浏览 1提问于2014-01-23得票数 3
问题是：
以最小的时间复杂度将k排序数组与n个元素合并到一个大小为nk的数组中。该算法应该是一个基于比较的算法。不应对输入作出任何假设。
因此，我知道有一种解决nklogk时间复杂性问题的算法，如这里所提到的：。
不过，我的问题是，我们能不能比nklogk少排序，这意味着，运行时是o(nklogk)。
于是我在网上搜索并找到了这样的答案：
它声称将一个大小为K的数组划分为单个数组，并将它们合并到一个数组中。但是这是不正确的，因为人们可以说他找到了一种解决sqrt(n)klogk问题的算法，即o(nklogk)但是n=1，所以我们在KlogK时间对数组进行排序，这与数组排序的下限并不矛盾
浏览 5提问于2022-05-22得票数 0
该算法在从arrl开始，以depr.I结束的特定时间间隔内寻找最重叠的活动(带)，对O(nlogn)的时间复杂度采用快速排序，然后用带O(n)的with循环来计算这些间隔的冲突活动的个数1，这样的O(nlogn) + O(n)时间复杂度是否类似于O(Nlogn)+ O(n)的时间复杂度?3.最后，理论上，对O(n)时间复杂度可以使用Tim排序吗？
用C编写的代码是为15个活动编写的，但假设它是通用的，并且带有未排序的arrl和depr
编辑:结果是1小时内最多的活动。
void findMaxBands(int n,int arr1[n],int depr[n]);
void quickSor
浏览 1提问于2018-12-03得票数 0
回答已采纳
3回答
我正在学习不同的排序算法及其时间/空间复杂度，并看到冒泡排序和插入排序等算法的空间复杂度为O(1)。
这让我感到奇怪，因为最低的空间复杂度肯定是O(n) (例如，存储数据集所需的内存，仅此而已)？
浏览 1提问于2017-05-10得票数 7
回答已采纳
1回答
def mysort1(x):
y = list(x)
y.sort()
z = [0]*len(y)
for i in range(0, len(y)):
z[i] = y[i]
return z
def mysort2(x):
y = list(x)
y.sort()
z = []
for i in range(0, len(y)):
z.insert(0,y[len(y)-i-1])
return z
考虑到两种方法的循环次数都是n次，我认为这两种方法都具有线性时间复杂度。
浏览 3提问于2022-09-20得票数 0
在我的课本上，有人告诉我排序问题的时间复杂度是θ(n*log(n))。但是，很容易说明基数排序是O(n)。这不是与所说的相矛盾吗？排序问题的时间复杂度下限不是这样的θ(n)吗？
编辑: StackOverflow不允许我在标题中使用"problem“，所以"problemo”必须保留。
浏览 9提问于2017-12-13得票数 2
回答已采纳
我知道空间复杂度从O(n)下降到O(log )。但是时间复杂度又如何呢？执行Quick Sort的时间是否与常规版本相同？
浏览 0提问于2011-11-06得票数 0
存在一个与数组相关的问题，要求时间复杂度为O(n)，空间复杂度为O(1)。
例如，如果我使用Arrays.sort(arr)，并将for循环用于一个pass循环：
public static int hello(int[]A){
Arrays.sort(A);
for(int i=0;i<A.length;i++){
....................
}
return ....;
}
因此，循环将花费O(n)时间。我的问题是：Arrays.sort()会花费更多时间吗？如果我使用Arrays.sort()，这一次的复杂性还会是O(n)吗？Arrays.s
浏览 0提问于2014-03-21得票数 26
回答已采纳
证明了在平面上n个点的凸壳可以用O(n)时间来计算，如果每个点的每个坐标都是形式p/q的有理数，且p和q有界值。
注:这是作业问题。我只想用贾维斯三月，通过某种方式避免扫描所有的点。也许这可以通过向固定的方向(使用有理条件)来检查下一个点的位置来实现。
浏览 5提问于2013-02-06得票数 2
回答已采纳
2回答
例如，如果我对某个数据结构有一个递归算法
Algo(Tree T)
if T == null
return false
...
当树为空时，该算法的最佳情况会出现吗？时间复杂度为O(1)？
浏览 5提问于2020-06-26得票数 0
3回答
有人能解释一下为什么快速排序的最佳运行时间不是线性的吗？有没有办法使快速排序的最佳运行时成为线性的？如果是这样，为什么它们通常不在实践中使用？
浏览 0提问于2013-02-26得票数 0
public static int partitionsimple_hoare(int[] arr,int l , int h){
int pivot = arr[l];
int i = l-1;
int j = h+1;
while(true){
do{
i++;
}while(arr[i]<pivot);
do{
j--;
}while(arr[j]>pivot);
if(i<j){
s
浏览 0提问于2017-09-21得票数 1
1回答
堆算法时间复杂度
、、、、
有人能告诉我维基百科，中这个堆算法的时间复杂度到底是多少吗？
我搜索了几个网站，答案都很模糊，有些人说时间复杂度是O(N!)有些人说这是O(NlogN)。哪一个是正确的答案？为什么？
谢谢。
浏览 3提问于2017-03-18得票数 5
回答已采纳
虽然我知道这似乎是显而易见的，但我会解释我的困惑。我一直认为快速排序的最坏情况时间复杂度是O(n^2)。[Arrays.sort(int[])]()从Java 7到Java 13的文档说:该算法在上提供O(n log(n))性能--许多数据集导致其他快速数据集退化为二次性能，并且通常比传统的(单轴)快速排序实现更快。
这里的关键字是“多”，所以我假设这里的O(n log(n))指的是平均情况，而且仍然存在导致O(n^2)最坏情况的数据集。
但是在Java14和更高版本中，[Arrays.sort(int[])]()的文档说:该算法在所有数据集上提供O(n (N))性能。
那么，对于现在改进的快
浏览 6提问于2022-03-16得票数 2
回答已采纳
1回答
我知道，在计算算法的时间复杂度时，我们应该放弃非占优项.我想知道在计算空间复杂性时是否应该放弃它们。例如，如果我有一个N个字母串，我想：
从字符串-> Space: O(N)构造一个字母列表；排序这个列表->最坏情况下的空间复杂性(我使用->)：O(N).
在这种情况下，整个解是取O(N) + O(N)空间还是只取O(N)？
谢谢。
浏览 4提问于2019-12-23得票数 0
最近我被要求在一次面试中创建一个就地排序算法。后续工作是对其进行编码，使其比O(n logn)更快，讨论每个循环的时间复杂性。
我知道插入排序、冒泡排序、堆排序、快速排序和shell排序都是合适的，然而，其中哪些可以修改以具有更好的时间复杂度？
浏览 1提问于2022-02-12得票数 0
我必须完成一个关于数字算法分析的研究。我需要一些关于这个主题的专家意见。据我所知，两个算法的时间复杂度相同，受复杂度方程中的常数影响，比如α。具有较大alpha值的算法被认为比具有较小alpha值的算法更差。复杂性的一个例子是F(n)=A(n^2+2n)
在时间复杂度相同的情况下，还有哪些因素控制着两种算法之间的比较？任何建议都将非常受欢迎。
浏览 6提问于2013-04-21得票数 0
回答已采纳
例如，如果我有一组数字，我在一维数组中填充一个副本，在二维数组中填充一个副本。所以从本质上讲，我有，并将始终在每个数组中有相等数量的元素。在这种情况下，时间复杂度是否真的不同，记住元素的数量将总是相等的？
浏览 0提问于2018-05-25得票数 1
在进行分类时，有些人建议在Java中使用stream().sorted或list.sort()方法来降低时间复杂度。然而，我认为这些方法也使用了一些时间复杂度相似的排序算法。
List result = list.stream().sorted((o1, o2)->o1.getItem().getValue().
compareTo(o2.getItem().getValue())).
collect(Collectors.toList());
那么
浏览 22提问于2022-02-06得票数 1
我准备参加一次面试，我想知道在我编写的下面的代码中，find_missing函数的时间复杂性是什么，它在1到99之间的一个未排序的值列表中找到了缺失的值。在使用内置排序的函数时，我对复杂性理论还不太熟悉，也不确定如何正确计算它。
def find_missing(num_array):
num_array = sorted(num_array)
print(num_array)
for k in range(len(num_array)-1):
if num_array[k] == num_array[k+1] - 1:
cont
浏览 0提问于2021-06-06得票数 1
回答已采纳
3回答
排序与插入的大O运行时间
、、、、
因此，如果您使用快速排序来对数组进行排序，则可以使用快速排序在O(nlogn)中进行排序，然后在排序之后，可以使用二进制搜索算法将新元素插入到O(logn)中的数组中。
我的问题是，有没有一种方法可以证明，如果可以在O(logn)时间内插入到排序数组中，这意味着排序算法必须至少是O(nlogn)？
换句话说，这两种算法的运行时间之间是否存在关系？
浏览 0提问于2012-11-06得票数 0
1回答
我遇到了一个数组排序算法，它看起来很好，但是它使用子数组递归。我听说制作一个子数组的时间复杂度是O(n)，这或多或少会阻止任何有效的排序使用子数组。
算法：
转一转。出于演示的目的，我们每次都将它称为数组中的最后一个数字。
将枢轴放在正确的位置。在这里，你会看到2和6，如果6大于2，就把它放在2之后。然后看1和2，如果它小于，就把它放在左边。如果两个数字相等，我选择将轴心放在左边。
取枢轴左侧和右侧的子数组，并在这些子数组上循环。
当子数组大小为1时停止。
一个有效的例子：
6 1 7 8 6 9 1 2 Pivot would be 2
1 1 2 6 6 7 8 9
浏览 0提问于2015-11-14得票数 1
2回答
给定一个整数数组，在最坏的情况下，时间复杂度是多少？
我认为这可以在O(n)中通过使用计数、排序或异或来实现。我说得对吗？
问题并不担心空间的复杂性和答案，O(Nlgn)说.
浏览 1提问于2016-08-30得票数 0
回答已采纳
1回答
所以我想知道如果我们使用一个键，排序函数的时间复杂度是多少，我知道它通常是nlogn，但对于下面的情况是一样的吗？
a=[[(1, 4,),1], [(2, 4), 10], [(1, 3), 11], [(2, 3), 5], [(3, 4), 7]]
a=sorted(a, key = lambda x: x[1],reverse=True)
因此，这里我根据第二个元素对列表进行了排序，因此时间复杂度是保持不变，即nlogn，还是有所不同
浏览 0提问于2020-10-08得票数 0
我试图确定以下算法的最佳情况和最坏情况，但由于我们的教授声称算法的最佳情况和最坏情况是“相同的”，所以我真的很困惑。
import math
def sum(Arr, left, right):
if(left>right):
return 0
elif(left == right):
return Arr[left]
else:
mid = left+ math.floor((right-left)/2)
leftSum = s
浏览 4提问于2022-02-08得票数 0
回答已采纳
1回答
在最近的一次面试中，我被问到了这个问题。
给定一个整型数组，其中除一个数字外的所有数字都出现一次，并且恰好有一个数字出现3次。在O(1)空间和O(n)时间复杂度中找到该数字。
我该如何处理这个问题？
浏览 0提问于2017-11-26得票数 1
8回答
在线性时间内排序？
、、、
给定范围为0..n^3-1的n个整数的输入集，提供线性时间排序算法。
这是我周四考试的复习，我不知道如何处理这个问题。
浏览 0提问于2009-04-14得票数 24
回答已采纳
1回答
考虑一些时间复杂度为n-logn的函数。那么这里的负号表示。
它的复杂度将包括-logn，并且它将小于n，或者它将更多地包含它作为logn操作，并且它将>n？
浏览 0提问于2017-04-05得票数 0
2回答
我对此有疑问；
我有一个这样的班级
class myCLass {
private:
string name;
float value;
public:
float getValue();
};
我有超过1,000,000个对象，我必须根据其值对这些项进行排序。所以我创建了指针列表；
list<myClass *> objectList;
然后用超过1.000.000个对象填充它。现在你可以说向量是最好的方法，如果你的对象小于30-40位，这是绝对正确的，然后我创建了它；
bool ec(myClass *s1, my
浏览 1提问于2013-10-14得票数 1
2回答
我用Java创建了一个非常简单的链表：
public class LinkedList {
class Node {
public Node next;
public int item;
public Node (int item) {
this.item = item;
}
}
int listSize = 0;
Node first = null;
Node last = null;
public void add(int n) {
浏览 2提问于2017-09-19得票数 0
2回答
凸包算法修正问题
、、
我最近在一次面试中被问到这个问题，但我不知道最佳的方法是什么。有人能帮我找到正确的方向吗。
期望时间复杂度为O(nlogn)，所需空间复杂度为O(1)。
浏览 0提问于2018-03-06得票数 0
回答已采纳
1回答
这不是家庭作业问题。我正在为一次面试做准备，并且对这个上的链接做了很多研究。我根据一项建议编写了一个解决方案，但我不同意提议的时间复杂性。我想知道我的断言是否不正确。
下面是一个函数，用来吐出一组字谜。它对每个输入单词进行排序，并将排序后的输入单词放入字典中。我自己编写的代码是基于发布的一条提示编写的，提示如下：
使用排序:我们可以对字符串数组进行排序，以便所有的字谜集合在一起。然后通过线性遍历排序数组来打印所有的字谜。该解决方案的时间复杂度为O(mnLogn) (我们将在排序中进行O(nLogn)比较，而比较则需要O(m)时间)。其中n是字符串的数目，m是字符串的最大长度。
我不同意
浏览 1提问于2020-03-04得票数 0
回答已采纳
1回答
我们的老师没有教我们如何分析算法的运行时间，然后她想让我们报告Shell排序。
我只想知道是否有一种简单的方法可以找到像shell排序这样的算法的平均/最佳/最坏情况的性能。
//for references
class ShellSort{
void shellSort(int array[], int n){
//n = array.length
for (int gap = n/2; gap > 0; gap /= 2){
for (int i = gap; i < n; i += 1) {
int temp = array[
浏览 16提问于2020-02-29得票数 0
回答已采纳
1回答
下面算法的时间复杂度是O(log(n))，但我只是好奇for循环的时间复杂度是多少？
func TwoNumberSum(array[] int, target int)[] int {
sort.Ints(array)
left, right: = 0, len(array) - 1
for left < right && left >= 0 && right < len(array) {
if array[left] + array[right] == target {
ret
浏览 4提问于2022-08-17得票数 2
C#的List<T>.Sort()的时间复杂度是什么
我猜是o(N)
但在我搜索了很多次之后，我没有得到任何准确的结果。
浏览 7提问于2012-03-08得票数 17
回答已采纳
我正在尝试设计一种算法来查找数组中两个相同元素的索引。输入是一个数组，输出是两个索引i&j，使得arrayi=arrayj。时间复杂度必须为O(nlogn)。
这是我尝试过的
let i=0 to size_of_array{
let j=i+1 to size_of_array{
if array[j]=array[i]{
print(i, j)
}
}
}
嵌套循环是O(n^2)，但如果我尝试这样设计。时间复杂度是多少？
N是数组的大小，我的实现将运行O(n(n-1)+(n-2)+(n-3)....+1)次。它
浏览 1提问于2019-09-17得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
