h**o 发帖数: 548 | 1 书上用对半排除法为什么就是time = O(n), 是否有问题那?
fetch(a, i, col) 需 O(1), 所以 把一个a[i]排除掉就需lg(n), 把所有奇/偶a[i]排
除掉就需n * lg(n),这本身就需 time = O(n lgn). 所以这道题time complexity 应
该是 nlgn, 还不如直接用bitmap(求a[i],然后把a[i]bitmap) 来做呢。
请问我的理解是否对, partition然后排除法好在那儿那 | i****y 发帖数: 84 | 2 n + 1/2 n + 1/4 n + 1/8 n + ..... < 2 n
So it is O(n). | k*j 发帖数: 153 | 3 把一个a[i]排除掉只需要O(1)
只需检查 a[i] && (1<
【在 h**o 的大作中提到】 : 书上用对半排除法为什么就是time = O(n), 是否有问题那? : fetch(a, i, col) 需 O(1), 所以 把一个a[i]排除掉就需lg(n), 把所有奇/偶a[i]排 : 除掉就需n * lg(n),这本身就需 time = O(n lgn). 所以这道题time complexity 应 : 该是 nlgn, 还不如直接用bitmap(求a[i],然后把a[i]bitmap) 来做呢。 : 请问我的理解是否对, partition然后排除法好在那儿那
| h**o 发帖数: 548 | 4 明白了。 xiexie.
【在 k*j 的大作中提到】 : 把一个a[i]排除掉只需要O(1) : 只需检查 a[i] && (1<
|
|