数基转换的时间复杂度
Time complexity of number base conversion
problem 8.3-4的答案：
- 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 ....
假设我们可以在 O(n) 时间内将 0 到 n^2-1 范围内的 n 整数转换为基数 n？
这怎么可能？
难道每次转换都需要 O(log(n)) 时间，因此对于 n 次转换，时间应该是 O(nlogn) 而不是 O(n) 吗？
我假设作者的意思是每个整数运算都在 O(1) 时间内完成，因此将数字转换为基数 n 基本上是最高有效位：x/n，租用有效位： x%n，在上述假设下是在常数时间内完成的。
如果没有给定的假设，每个数字需要 log(n^2)=2log(n) 位来表示，因此仅读取输入将花费 O(nlogn) 时间，因此需要此假设来满足时间要求。
problem 8.3-4的答案：
- 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 ....
假设我们可以在 O(n) 时间内将 0 到 n^2-1 范围内的 n 整数转换为基数 n？
这怎么可能？
难道每次转换都需要 O(log(n)) 时间，因此对于 n 次转换，时间应该是 O(nlogn) 而不是 O(n) 吗？
我假设作者的意思是每个整数运算都在 O(1) 时间内完成，因此将数字转换为基数 n 基本上是最高有效位：x/n，租用有效位： x%n，在上述假设下是在常数时间内完成的。
如果没有给定的假设，每个数字需要 log(n^2)=2log(n) 位来表示，因此仅读取输入将花费 O(nlogn) 时间，因此需要此假设来满足时间要求。