计数排序的时间复杂度 [英] The time complexity of counting sort

问题描述

我正在学习算法课程，在那里我看到计数排序的时间复杂度为O(n + k)，其中k是数字范围，n是输入大小.我的问题是，当k和n之间的差异太大时，例如当k = O(n ² )或O(n ³ )时，我们可以说复杂度是O(n ² )还是O(n ³ )?那么在这种情况下，计数排序不是一个明智的方法，我们可以使用合并排序.我对吗?

I am taking an algorithms course and there I saw that the time complexity of counting sort is O(n+k) where k is the range of numbers and n is the input size. My question is, when the difference between k and n is too much, such as when k=O(n²)or O(n³), can we say that the complexity is O(n²) or O(n³)? Then in this case counting sort is not a wise approach and we can use merge sort. Am I right?

推荐答案

是的，您在所有方面都完全正确.

Yes, you are exactly right on all counts.

此外，我们可以做出更强的陈述:当k = O(n ² )或O(n ³ )时，我们可以说计数排序的复杂性是Θ(n ² )或Θ(n ³ ).

Furthermore, we can make stronger statements: when k=O(n²) or O(n³), we can say that the complexity of the counting sort is Θ(n²) or Θ(n³).

这篇关于计数排序的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！