mr boombastic wrote:
насчёт divide and conquer я не прав но мой пойнт был в том что через master theorem нельзя доказать randomized версию quicksort в чистом виде. если посмотреть то они там предполагают что в наихудшем случае это разбиение будет на 0 и (n-1) и оттуда уже пляшут. но в randomized версии эти разбиения случайные.
А вот вам пример из вашей любимой Курсеры где Тим доказывает линейное время исполнения RandomizedSelect используя MasterMethod (MasterTheorem) для average case. https://class.coursera.org/algo-003/lecture/36
Tarasik wrote:
Master Method как средство вычисления времязатрат алгоритма подходит везде где используется рекурсия.
везде?
везде где неизменная зависимость выполнения вызываемой и вызывающей функции, как мне кажется т.е. a > 1 a константа. и есть еще некоторе исключения т.е. почти во всех случаях
Last edited by Tarasik on 07 Mar 2013 23:46, edited 1 time in total.
mr boombastic wrote:я вообще заметил что про с,
как найти k-ый элемент в не отсортированном массиве?
к-ый по величине.
Делается похоже на quick sort в том плане что используется partitioning. Берем pivot и перебрасываем влево от него то что больше и вправо то что меньше (partitioning).
Если pivot оказывается в позиции больше k то делаем то же самое с левой частью от pivot и продолжаем искать элемент k.
Если меньше - то в правой части таким образом ищем элемент indexOf(pivot) - k. И так рекурсивно продолжаем искать пока pivot не совпадет с k
Удивительно но это займет линейное время (если считать используя master method).
Обычно спрашивают худшее время а не среднее, и оно у вас не линейное.
mr boombastic wrote:
насчёт divide and conquer я не прав но мой пойнт был в том что через master theorem нельзя доказать randomized версию quicksort в чистом виде. если посмотреть то они там предполагают что в наихудшем случае это разбиение будет на 0 и (n-1) и оттуда уже пляшут. но в randomized версии эти разбиения случайные.
А вот вам пример из вашей любимой Курсеры где Тим доказывает линейное время исполнения RandomizedSelect используя MasterMethod (MasterTheorem) для average case. https://class.coursera.org/algo-003/lecture/36
супер!!!! заметьте какие assumptions идут.
best pivot: the median!(but this is circular) и только потом рекуррентное соотношения.
ткните на следующее видео и увидите "нормальный" proof.
You do not have the required permissions to view the files attached to this post.
mr boombastic wrote:
насчёт divide and conquer я не прав но мой пойнт был в том что через master theorem нельзя доказать randomized версию quicksort в чистом виде. если посмотреть то они там предполагают что в наихудшем случае это разбиение будет на 0 и (n-1) и оттуда уже пляшут. но в randomized версии эти разбиения случайные.
А вот вам пример из вашей любимой Курсеры где Тим доказывает линейное время исполнения RandomizedSelect используя MasterMethod (MasterTheorem) для average case. https://class.coursera.org/algo-003/lecture/36
супер!!!! заметьте какие assumptions идут.
best pivot: the median!(but this is circular) и только потом рекуррентное соотношения.
ткните на следующее видео и увидите "нормальный" proof.
Я его видел. Но если вы его выведете в Амазоне на доске то вас могут не взять - сочтут шыбко умным (overqualified)
В худшем случае квиксорт сортирует за квадратное время. Но почему то именно он используется (с модификациями) в известных мне системах. Посмотрите ка исходники Джавы и дотНета.
В худшем случае квиксорт сортирует за квадратное время. Но почему то именно он используется (с модификациями) в известных мне системах. Посмотрите ка исходники Джавы и дотНета.
Я смотрел исходники сортировки на джаве, и разных стд либ си, везде используется не чистый qsort а гибрид с merge sort. Но это к делу не относится, я просто обратил внимание что на интервью обычно спрашивают худшее время, и ваш вариант не оптимальный по этой характеристике.
В худшем случае квиксорт сортирует за квадратное время. Но почему то именно он используется (с модификациями) в известных мне системах. Посмотрите ка исходники Джавы и дотНета.
В худшем случае квиксорт сортирует за квадратное время. Но почему то именно он используется (с модификациями) в известных мне системах. Посмотрите ка исходники Джавы и дотНета.
Я смотрел исходники сортировки на джаве, и разных стд либ си, везде используется не чистый qsort а гибрид с merge sort. Но это к делу не относится, я просто обратил внимание что на интервью обычно спрашивают худшее время, и ваш вариант не оптимальный по этой характеристике.
Как ни странно, обычно последние 10 элементов используют не merge, а insertion sort. Мердж не хорош дополнительными буферами, и его применение в наше время в основном во внешних/параллельных сортировках.
В худшем случае квиксорт сортирует за квадратное время. Но почему то именно он используется (с модификациями) в известных мне системах. Посмотрите ка исходники Джавы и дотНета.
Я смотрел исходники сортировки на джаве, и разных стд либ си, везде используется не чистый qsort а гибрид с merge sort. Но это к делу не относится, я просто обратил внимание что на интервью обычно спрашивают худшее время, и ваш вариант не оптимальный по этой характеристике.
Как ни странно, обычно последние 10 элементов используют не merge, а insertion sort. Мердж не хорош дополнительными буферами, и его применение в наше время в основном во внешних/параллельных сортировках.
В худшем случае квиксорт сортирует за квадратное время. Но почему то именно он используется (с модификациями) в известных мне системах. Посмотрите ка исходники Джавы и дотНета.
Я смотрел исходники сортировки на джаве, и разных стд либ си, везде используется не чистый qsort а гибрид с merge sort. Но это к делу не относится, я просто обратил внимание что на интервью обычно спрашивают худшее время, и ваш вариант не оптимальный по этой характеристике.
Мердж не хорош дополнительными буферами, и его применение в наше время в основном во внешних/параллельных сортировках.
Вроде как достаточно просто сконструировать inplace merge sort без дополнительных буферов.
в джаве по моему мердж сорт для обьектных типов и квик сорт для примитивных так как квик сорт не стабилен и может относительный порядок одинаковых элементов поменять.
Вызор итеративного интросорта, и в конце инсершн. интросорт это лефт рекурсив квиксорт, пока массив не станет размера S. Потом инсершн сорт всё ставит на свои места.
