我正在学习算法课程，在那里我看到计数排序的时间复杂度是O（n + k），其中k是数字范围，n是输入大小。我的问题是，当k和n之间的差异太大时，例如当k = 0（n2）或O（n3），我们可以说复杂性是O（n2）或O（n3）？然后在这种情况下计数排序不是一个明智的方法，我们可以使用合并排序。我对吗？
我正在学习算法课程，在那里我看到计数排序的时间复杂度是O（n + k），其中k是数字范围，n是输入大小。我的问题是，当k和n之间的差异太大时，例如当k = 0（n2）或O（n3），我们可以说复杂性是O（n2）或O（n3）？然后在这种情况下计数排序不是一个明智的方法，我们可以使用合并排序。我对吗？
是的，你完全正确。
此外，我们可以做出更强有力的陈述：当k = O（n2）或O（n3），我们可以说计数排序的复杂性是Θ（n2）或Θ（n3）。
是的，你完全正确。
此外，我们可以做出更强有力的陈述：当k = O（n2）或O（n3），我们可以说计数排序的复杂性是Θ（n2）或Θ（n3）。
理论上，你仍然可以在O（n）时间内排序。如果值的范围是1到n3 然后转换为base n并进行基数排序。在base n中，数字有3位数，因此基本转换的运行时间为O（3n + 3n）+ O（n）。总体O（n）。