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<
|
|
