Randomized Insertion Sort

Курсы → Design and Analysis of Algorithms II ↓

18й видео-выпуск, поднимаем тему алгоритмов. В первой части – короткое введение в статистику и формулы, необходимые для рандомизации. Во второй части – применение в алгоритме сортировки insertion sort и доказательство уменьшения времени работы алгоритма в два раза (по сравнению с худшим случаем). Простите, пользователи Ютуба, пока видео только на вимео, а через несколько часов будет в подкаст-ленте. Чтобы выложить видео на Ютуб видео придется резать на кусочки по 10 минут.

Часть 1

Смотреть в HD на Vimeo

Часть 2

Смотреть в HD на Vimeo

Напомню, что при желании видео можно скачать на их страницах на vimeo (в правом нижнем углу).

17 Янв 2010 by freetonik

6 Responses to Randomized Insertion Sort

pluton

Январь 17th, 2010 at 20:36

freetonik, спасибо за объяснение. а сколько раз нужно перемешать массив для получения "среднего" распределения? не будет ли это дольше, чем самый худший способ в обычном алгоритме?
ps. expected value — математическое ожидание

freetonik

Январь 17th, 2010 at 21:40

один раз, после этого набор уже будет случайным
спасибо!

ashagi

Январь 18th, 2010 at 0:09

Очень полезное видео для всех начинающих джедаев :) Кстати, было бы очень полезно, если бы в конце делал небольшое summary, описывая все основные пункты. А так, отличный материал! Respect :)

freetonik

Январь 18th, 2010 at 0:11

Буду иметь ввиду, спасибо за совет!