O(n)如果数组只包含k ? ?>0(k是常量)不同的元素,那么在最坏的情况下运行时可以对数组进行排序吗？
假设它需要恒定的时间来比较其中包含n元素的数组.
首先,我想了解任务,他们想要什么？我理解这个假设.但是k ? ?>0(k是一个常数)不同的元素究竟是什么意思呢？
这是否意味着我们得到了一个数组,它的大小是k因为它说?>0数组大小不能0？那是对的吗？如果是这样,我不太明白为什么他们不只是用n元素代替数组而不是它.
无论如何,这就是我理解它的方式,我会说在最坏的情况下运行时不可能对这个数组进行排序,O(n)因为如果我们看一下桶排序/基数排序等,就可以完成O(n*logn).