2
Мне интересно, почему QuickSelect должен быть таким хорошим алгоритмом для нахождения произвольного элемента из n-size, unsorted set. Я имею в виду, когда вы проходите через все элементы один за другим, пока не найдете нужный результат, он сравнил O (n). Это самый лучший случай quickselect и намного проще.QuickSelect против линейного поиска
Я пропустил что-то важное в этом вопросе? Есть ли случай, когда QiuckSelect работает лучше, чем линейный поиск?
Как бы вы найти 'k'-й по величине элемент с линейным поиском? –
ах, вот что мне не хватало! Я не думал о том, чтобы найти k-й самый большой/наименьший элемент. Спасибо! – wodzu