radix是O(k^2)吧，k个数，每个数字k位 【 在 hopper (圆环套圆环娱乐城总经理王某) 的大作中提到: 】 : 将这些数字看成n进制，使用radix-sort. : The running time is O(4n) = O(n) : The radix sort running time is O(d * (n + k)) , where d is the number of : digit, n is the number of elements, and k is the number of possible values. : In this case, k equals n. So the total running time is O(2 * (n + n)) = O(4n : ) = O(n)
这个题怎么解？
Yash is a student at MIT and has to do a lot of work. He has finished k
homeworks and the deadlines of these homeworks lie between 0 to 𝑘^2 - 1.
Help Yash sort these homeworks in non-decreasing order of deadlines with
expected time and space complexity O(k).
Test Case 1:
Input: k = 5, homeworks = [13, 24, 1, 17, 8]
Output: [1, 8, 13, 17, 24]
https://algomart.quora.com/?__ni__=0&__tiids__=34496228&__filter__=all&__
nsrc__=notif_page&__sncid__=17590302065&__snid3__=24647767134#anchor
将这些数字看成n进制，使用radix-sort.
The running time is O(4n) = O(n)
The radix sort running time is O(d * (n + k)) , where d is the number of
digit, n is the number of elements, and k is the number of possible values.
In this case, k equals n. So the total running time is O(2 * (n + n)) = O(4n) = O(n)
radix是O(k^2)吧，k个数，每个数字k位
【 在 hopper (圆环套圆环娱乐城总经理王某) 的大作中提到: 】
: 将这些数字看成n进制，使用radix-sort.
: The running time is O(4n) = O(n)
: The radix sort running time is O(d * (n + k)) , where d is the number of
: digit, n is the number of elements, and k is the number of possible values.
: In this case, k equals n. So the total running time is O(2 * (n + n)) = O(4n
: ) = O(n)
bucket sort, take sqrt firstly, which gives bucket。 在每个bucket里面再sort
一下，因为只有k个，所以k个bucket每个bucket里面average个数应该是1. Worsecase
都在一个bucket里面，需要看klog（k)再sort一下
我也想了一个解:
先对每个数取log_2()，然后counting sort，从1到k，按照hashtable建立各个bucket chain，这样期望的时间空间复杂度应该都是O(k)
取log_2可能会拥挤在少数bucket里面，按照题设应该是sqrt
【 在 BroPingtou (ǢŦĦȆȐ) 的大作中提到: 】
: 我也想了一个解:
: 先对每个数取log_2()，然后counting sort，从1到k，按照hashtable建立各个
bucket
: chain，这样期望的时间空间复杂度应该都是O(k)
没毛病，像hashtable那样放个linkedlist就好了
反正这些list期望长度都是1
update:跟你的一样吧，取sqrt的问题是不是还剩2^{k/2}个bucket，还是太多了
【 在 Caravel (克拉维尔) 的大作中提到: 】
: 取log_2可能会拥挤在少数bucket里面，按照题设应该是sqrt
: bucket
取值范围(0, 𝑘^2- 1)， sqrt之后（0，k), 如果是log2的话（0， 2*log2（K))
, log2(k) << k when k is large，所以可能时间复杂度满足要求。
【 在 BroPingtou (ǢŦĦȆȐ) 的大作中提到: 】
: 没毛病，像hashtable那样放个linkedlist就好了
: 反正这些list期望长度都是1
: update:跟你的一样吧，取sqrt的问题是不是还剩2^{k/2}个bucket，还是太多了
我傻逼了，看成了2^k
【 在 Caravel (克拉维尔) 的大作中提到: 】
: 取值范围(0, 𝑘^2- 1)， sqrt之后（0，k), 如果是log2的话（0， 2*log2
（K
: ))
: , log2(k) << k when k is large，所以可能时间复杂度满足要求。