11 sorting algorithm asymptotic-complexity
我正在学习算法课程,在那里我看到计数排序的时间复杂度是O(n + k),其中k是数字范围,n是输入大小.我的问题是,当k和n之间的差异太大时,例如当k = O(n 2)或O(n 3)时,我们可以说复杂度是O(n 2)或O(n 3) ？然后在这种情况下计数排序不是一个明智的方法,我们可以使用合并排序.我对吗？
NPE*_*NPE 10
是的,你完全正确.
此外,我们可以做出更强有力的陈述:当k = O(n 2)或O(n 3)时,我们可以说计数排序的复杂度是Θ(n 2)或Θ(n 3).
归档时间：
12 年，5 月 前
查看次数：
10627 次
最近记录：
12 年，2 月 前