假设我有一个大小为n的数组，这个数组的最大值是k。
让我们假设k=log(sqrt(n))和我想以最有效的方式对这个数组进行排序，为此我已经简化了方程式以k得到n并且我得到了n=2^2k这是我的数组大小。
现在，如果我应用Θ(n^(2))的任何排序算法，时间复杂度将等于Θ(2^(4k)) n这将是Θ(n^2)，如果我应用Θ(nlogn)排序算法，我将有Θ(k*2^(2k))，并且在ni方面将有Θ(nlog(sqrt(n)))这是最有效的时间复杂性，我这样做了吗？
如果我假设k=n^n可以使用我以前使用的相同方法吗？为此，我没有用k表示使用相同方法的数组大小，还有另外一种方法吗？
知道要排序的数组中的最大元素值k可能会有所帮助，尤其是在k <n的情况下。在这种情况下，您可以使用counting sort，运行时间为O（n + k）