考虑这个问题:
A comparison-based sorting algorithm sorts an array with
n
items. For which fraction ofn!
permutations, the number of comparisons may becn
wherec
is a constant?
我知道对包含任意项的数组进行排序的最佳时间复杂度是 O(nlogn)
并且它不依赖于任何顺序,对吧?因此,没有导致 cn
比较的分数。如果我错了,请指导我。
最佳答案
这取决于您使用的排序算法。
Optimized Bubble Sort例如,比较数组的所有相邻元素,并在左侧元素大于右侧元素时交换它们。重复此操作,直到没有执行交换为止。
当你给冒泡排序一个排序数组时,它不会在第一次迭代中执行任何交换,因此在 O(n) 中排序。
另一方面,Heapsort将采用独立于输入顺序的 O(n log n)。
编辑:
要针对给定的排序算法回答您的问题,可能并不简单。 n中只有一个!排列已排序(为简单起见,假设没有重复项)。但是,对于 bubblesort 的示例,您可以(从排序数组开始)交换每对相邻元素。此输入将采用 Bubblesort 两次迭代,这也是 O(n)。
关于algorithm - n 个数字的排序时间是否取决于数字的排列?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48095766/