danlark·2 年前·議論3 and 4 elements will fail to prove the complexity is linearYou still can do 3 or 4 but with slight modificationshttps://arxiv.org/abs/1409.3600For example, for 4 elements, it's advised to take lower median for the first half and upper median for the second half. Then the complexity will be linear
danlark·2 年前·議論Around 4 years ago I compared lots of different median algorithms and the article turned out to be much longer than I anticipated :)https://danlark.org/2020/11/11/miniselect-practical-and-gene...
You still can do 3 or 4 but with slight modifications
https://arxiv.org/abs/1409.3600
For example, for 4 elements, it's advised to take lower median for the first half and upper median for the second half. Then the complexity will be linear