Comments 43
У кого-то есть весь материал этого курса скачаный с coursera(видео+презентахи)? Дело в том, что для этого курса больше нет возможности View class archive.
Нет.
www.coursera.org/course/algs4partI этот курс ищу.
www.coursera.org/course/algs4partI этот курс ищу.
Хм. У меня архив работает.
Хотя там ведь, вроде, два курса были: первый вел Тим Рафгарден без привязки к какому-либо ЯП, а второй с привязкой к Java вел, пардон забыл имя, крутой мужик из Адоби. Так вот я проходил курс у Рафгардена.
Хотя там ведь, вроде, два курса были: первый вел Тим Рафгарден без привязки к какому-либо ЯП, а второй с привязкой к Java вел, пардон забыл имя, крутой мужик из Адоби. Так вот я проходил курс у Рафгардена.
Вот-вот, та же беда. Поиск не дал результатов, в итоге лишь слайды смог найти, записался на следующую итерацию курса, чтобы иметь возможность скачать его целиком.
Это там где Robert Sedgewick и Kevin Wayne?
У меня есть (mp4 + pdf слайды, без задач), скачал когда понял что проходить вовремя нет времени.
Если на TPB по ссылке ниже не то, могу куда-то залить (1.1Gb)
У меня есть (mp4 + pdf слайды, без задач), скачал когда понял что проходить вовремя нет времени.
Если на TPB по ссылке ниже не то, могу куда-то залить (1.1Gb)
Если на списках, то merge +in-place.
Не очень понимаю, какая тут дана оценка, лучше было бы поставить асимптотичнчкую оценку, т.к может сложиться впечатление, что сортировка слиянием работает быстрее чем быстрая, что, вообще говоря не верно.
Вообще говоря не верно при каких условиях?
У сортировки слиянием оценка тета(nlogn) у быстрой O(nlogn) так что в теории быстрая может работать быстрее. Если я не напутал с оценкой сортировки слиянием
Между тем есть вероятность получить на быстрой сортировке O(N^2). На самом деле быстрая сортировка при прочих равных немного быстрее сортировки слиянием, за счет меньшего количестве перестановок (даже не смотря на то, что коэффициент при NlogN у быстрой сортировки не 1, а 2, если быть точнее, то там по-моему 1.39 в курсе проходила оценка). У сортировки слиянием свою плюсы… В общем между ними примерно паритет, выбор той или иной сортировки зависит от конкретных условий задачи.
Это да, быстрая до О(n^2) легко падает, вы правы в общем)
Ну как легко...) вероятность не очень высока, я бы даже сказал достаточно мала, при условии что перед сортировкой производится перемешивание входных данных.
Если поделится так, что в одной части 1 элемент а в другой n-1 будет квадрат, обратный порядок, например
ну собственно обратный порядок вроде и есть худший случай, при случайном перемешивании входных данных, вероятность такого события достаточно мала. не готов дать точную оценку вероятности.
Нет, обратный порядок это один из лучших случаев, особенно при выборе пивота посередине. Такой массив будет отсортирован уже после первой итерации, дальше будут только сравнения без обменов.
Если пивот выбирается случайным образом, то вероятность худшего случая 1/(N!), если не напутал, причем от входного массива не зависит. Т.е. зависит конечно, учитывая то, что генераторы псевдослучайны. При этом, если выбирать пивот по принципу выборки трех элементов массива, и выбора среднего из них, то вероятность соотвественно еще ниже.
Если пивот выбирается случайным образом, то вероятность худшего случая 1/(N!), если не напутал, причем от входного массива не зависит. Т.е. зависит конечно, учитывая то, что генераторы псевдослучайны. При этом, если выбирать пивот по принципу выборки трех элементов массива, и выбора среднего из них, то вероятность соотвественно еще ниже.
На удобном для быстрой сортировки наборе — конечно. Но нельзя сранивать несравнимые вещи — тета это не то же самое, что O в среднем.
Также есть реализации merge, которые в лучшем случае работают за O(N) — соответствено у них нет теты.
Кстати я вгляделся и перестал понимать таблицы в статье — что в них вообще содержится? Потому что это точно не O — у него нет констант.
Также есть реализации merge, которые в лучшем случае работают за O(N) — соответствено у них нет теты.
Кстати я вгляделся и перестал понимать таблицы в статье — что в них вообще содержится? Потому что это точно не O — у него нет констант.
поправьте если я не прав, но табличку по сортировкам можно так интерпретировать. worst case — O(), avr. case — тета(), best case — омега().
А где же heapsort? Тоже ведь эффективный алгоритм.
Я себе несколько лет назад приготовил небольшой конспектик по алгоритмам на основе Википедии: files.mail.ru/1APV8Y
Полезно, если надо освежить в памяти экзотические алгоритмы перед интервью.
А здесь files.mail.ru/39KWOB — более развернутый конспект (тоже на основе Википедии)
Полезно, если надо освежить в памяти экзотические алгоритмы перед интервью.
А здесь files.mail.ru/39KWOB — более развернутый конспект (тоже на основе Википедии)
Хороший конспект. Возьму на заметку.
UFO just landed and posted this here
Вот нагуглил парочку:
1) www.algolist.net/ (у меня в Опере верстка поехала — основной тексту уехал вниз)
2) www.cs.auckland.ac.nz/~jmor159/PLDS210/ds_ToC.html (субъективно слегка вырвиглазная графика и цвета)
1) www.algolist.net/ (у меня в Опере верстка поехала — основной тексту уехал вниз)
2) www.cs.auckland.ac.nz/~jmor159/PLDS210/ds_ToC.html (субъективно слегка вырвиглазная графика и цвета)
http://e-maxx.ru/algo
Сборник сделан Ивановым Максимом — выпускником мех-мата Саратовского ГУ, серебрянным призером чемпионата мира по программированию ACM-ICPC 2011.
Сборник сделан Ивановым Максимом — выпускником мех-мата Саратовского ГУ, серебрянным призером чемпионата мира по программированию ACM-ICPC 2011.
Эх, только закончили в универе первый курс по алгоритмам, как тут такая «шпоргалка»
Очень жаль, что закрыли материалы курса. Насколько я понял, это позиция Принстона.
Вторую часть, кстати, отложили на месяц.
Вторую часть, кстати, отложили на месяц.
Sign up to leave a comment.
Алгоритмы и структуры данных — шпаргалка