我正在进行一个算法课程，我发现计数排序的时间复杂度是O（n+k），其中k是数字的范围，n是输入大小。我的问题是，当K和N之间的差异太大时，例如当k＝O（n2）或O（n3）时，我们可以说复杂性是O（n2）还是O（n3）？在这种情况下，计数排序不是一种明智的方法，我们可以使用合并排序。我说得对吗？
最佳答案
是的，你在所有方面都是对的。
此外，我们可以做更有力的陈述：当k= o（n2）或O（n3）时，我们可以说计数排序的复杂度是（n2）或η（n3）。
我正在进行一个算法课程，我发现计数排序的时间复杂度是O（n+k），其中k是数字的范围，n是输入大小。我的问题是，当K和N之间的差异太大时，例如当k＝O（n2）或O（n3）时，我们可以说复杂性是O（n2）还是O（n3）？在这种情况下，计数排序不是一种明智的方法，我们可以使用合并排序。我说得对吗？
最佳答案
是的，你在所有方面都是对的。
此外，我们可以做更有力的陈述：当k= o（n2）或O（n3）时，我们可以说计数排序的复杂度是（n2）或η（n3）。