algorithm - 数基转换的时间复杂度

Question

problem 8.3-4 的答案:

8. 8.3-4 (from CLRS) Show how to sort n integers in range 0 to n^2 − 1 in O(n) time.

答案:

First take O(n) time to convert the integers into 2-digits numbers base n ....

假设我们可以将 0 到 n^2-1 范围内的 n 整数转换为 中的基数 n O(n) 时间？
这怎么可能？

难道每次转换都需要 O(log(n)) 时间，因此对于 n 次转换，时间应该是 O(nlogn) 而不是 O(n) 吗？

Answer 1

我假设作者的意思是每个整数运算都在 O(1) 时间内完成，因此将数字转换为基数 n 基本上是最高有效位: x/n, lease significant digit: x%n, 在上面的假设下是在常数时间内完成的。

如果没有给定的假设，每个数字都需要 log(n^2)=2log(n) 位来表示，因此仅读取输入将花费 O(nlogn) 时间，所以需要这个假设来满足时间要求。