SelectionSort. Однако,


SelectionSort. Однако, рассматривая более "мелкие" операции, мы обнаружим, что их количество уже зависит от контекста, и реальное время выполнения сортировок векторов окажется неодинаковым. Какой из векторов будет обработан быстрее всех, а какой - медленнее остальных? Упражнение #3. Эта задача предлагалась школьникам на городской олимпиаде по информатике в Санкт-Петербурге, точнее, еще в Ленинграде. Задан массив Mas[1..N], состоящий из 0, 1 и 2. Требуется перестроить его таким образом, чтобы все 0 оказались в начале массива, далее - все 1 и в конце - все 2. Можно ли обойтись одним просмотром массива? Как мы до сих пор ни старались, асимптотическая трудоемкость всех рассмотренных выше модификаций обменной сортировки оставалась одной и той же - квадратичной. Однако возможности улучшить эту оценку есть. Вспомним один из общих алгоритмических подходов к задаче, обсуждавшийся нами в Уроке A3, а именно, метод частных целей. Сейчас, как мы увидим, подходящей случаю окажется
Индекс
Элементарные функции    Линейные уравнения    Нелинейные уравнения    Случайные числа


Hosted by uCoz