排序算法的复杂性

-1

这里是一个排序算法，而不是一个聪明的算法。在这个版本中，当元素是非负的并且最多只发生一次时，它可以很好地工作。我对它的时间复杂性感到困惑。它是O（n）吗？那么比这个符号快速排序更好吗？谢谢。下面是代码：排序算法的复杂性

public int[] stupidSort(int[] array){ 

// Variables 
int max = array[0]; 
int index = 0; 
int[] lastArray = new int[array.length]; 

// Find max element in input array 
for(int i = 0; i < array.length; i++){ 
    if (array[i] > max) 
    max = array[i]; 
} 

// Create a new array. In this array, element n will represent number of n's in input array 
int[] newArray = new int[max + 1]; 

for (int j = 0; j < array.length; j++) 
    newArray[array[j]]++; 

// If element is bigger than 0, it means that number occured in input. So put it in output array 
for(int k = 0; k < newArray.length; k++){ 
    if(newArray[k] > 0) 
    lastArray[index++] = k; 
} 
return lastArray; 
}

来源

2017-02-25 aladinsane7

你写什么counting sort，它有O（n）的复杂性确实。但是，它不能与QuickSort相比，因为QuickSort是基于比较的算法。这2种算法属于不同的类别（你的是一个非比较，quicksort是一种比较算法）。您的算法（计数排序）假定数组中的数字范围是已知的，并且所有数字都是整数，而QuickSort适用于每个数字。

您可以通过排序算法0了解更多信息。在该链接中，您可以看到分为两类的排序算法的复杂性：比较和非比较。

EDIT

正如Paul Hankin指出复杂性不总是为O（n）。它是O（n + k）其中k是输入数组的最大值。下面引用是维基百科的文章中为counting sort解释的时间复杂度：

由于该算法只使用for循环简单，没有递归或子程序调用，这是简单的分析。计数数组的初始化以及在计数数组上执行前缀和的第二个for循环每个迭代最多k + 1次，因此需要O（k）次。另外两个for循环，以及输出数组的初始化，每个都花费O（n）次。因此，整个算法的时间是这些步骤的时间总和，O（n + k）。

来源

2017-02-25 18:48:58 Thanasis

感谢您的回答和建议。 – aladinsane7

不客气。您也可以将我的答案标记为已接受。谢谢：）！ – Thanasis

该算法不是O（n）。 'new int [max + 1]'（以及后面的'k'循环）需要O（'max'）时间，这个时间可能比'n'任意地更差。 –

给出的算法非常类似于计数排序。而QuickSort是一种基于比较模型的排序算法。只有在最坏的情况下，QuickSort给出了O（n^2）的时间复杂度，否则就是O（nlogn）。 快速排序与它一起使用随机化版本是枢轴随机选择，因此最糟糕的情况最经常以这种方式避免。

编辑：如在评论复杂paulhankin = O指出（N + K）更正：

你现在提出的代码使用计数根据排序，也就是数排序和你的代码的时间复杂度是O（n + k）。但是你必须认识到的是，这个算法取决于输入的范围，而范围可以是任何东西。此外，该算法不是InPlace而是稳定。在许多情况下，您想要排序的数据不仅是整数，而且数据可以是任何具有需要借助密钥进行排序的密钥的数据。如果稳定算法没有使用比在这种情况下排序可能有问题。

以防万一，如果有人不知道：

原地算法：是对在其中需要额外的空间是不依赖于给定的输入。

稳定算法：例如，如果在排序之前数据集中有两个5，那么在排序之前，排序之前排在第一位的5比排在第一位的优先。

编辑：（关于aladinsane7的评论）：是的countSort正式版本还没有处理这方面。如果你看一下CountSort就好了。其时间复杂度为O（n + k）。其中K说明了数据的范围，而n是剩余算法的复杂度。

来源

2017-02-25 18:54:37

谢谢。如果我们希望它适用于相同数字出现多次的情况，我们需要另一个循环以“newArray”运行。那么它的复杂性会是什么？有任何想法吗？ – aladinsane7

我对我的回答做了相关编辑。这将回答您的查询。 –

在你的回答中，你说时间复杂度毫无疑问是O（n），但后来你会说它是O（n + k）。后者是正确的，前者是不正确的。 –

排序算法的复杂性

回答

相关问题