Алгоритмы и структуры данных — шпаргалка

    Пару недель назад, необходимо было освежить информацию в голове информацию по структурам данных и алгоритмам для собеседования. Первым делом полез на www.coursera.org, где хотел пробежаться по некоторым лекциям курса Алгоритмы, там же были две сводные таблички, которые в процессе изучения курса взял на заметку — отлично помогали запомнить сложность операций. Но, к моему удивлению, материалы пройденного курса стали недоступны. Быстрое гугление, в надежде, что кто-нибудь выложил лекции на торрентах, к сожалению, не дало результатов. В итоге, я нашел полную коллекцию слайдов по данному курсу. Спешу поделиться. Самое главное, что взял из этих слайдов, — это вышеупомянутые сводные таблички. Думаю многим пригодится.

    Сортировки:


    Структуры данных:
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 43
      +2
      У кого-то есть весь материал этого курса скачаный с coursera(видео+презентахи)? Дело в том, что для этого курса больше нет возможности View class archive.
        0
        Хм. У меня архив работает.
        Хотя там ведь, вроде, два курса были: первый вел Тим Рафгарден без привязки к какому-либо ЯП, а второй с привязкой к Java вел, пардон забыл имя, крутой мужик из Адоби. Так вот я проходил курс у Рафгардена.
          +1
          Это не те курсы. Это Алгоритмы у Седживика (если конечно он не из Адоб).
            0
            Седжвик как раз таки член совета директоров Adobe Systems
              –7
              Как только Эдоуби не назовут…
            0
            Вот-вот, та же беда. Поиск не дал результатов, в итоге лишь слайды смог найти, записался на следующую итерацию курса, чтобы иметь возможность скачать его целиком.
              0
              Это там где Robert Sedgewick и Kevin Wayne?
              У меня есть (mp4 + pdf слайды, без задач), скачал когда понял что проходить вовремя нет времени.
              Если на TPB по ссылке ниже не то, могу куда-то залить (1.1Gb)
                0
                На TPB вроде то что нужно.
              0
              Если на списках, то merge +in-place.
                0
                Не очень понимаю, какая тут дана оценка, лучше было бы поставить асимптотичнчкую оценку, т.к может сложиться впечатление, что сортировка слиянием работает быстрее чем быстрая, что, вообще говоря не верно.
                  0
                  Вообще говоря не верно при каких условиях?
                    0
                    У сортировки слиянием оценка тета(nlogn) у быстрой O(nlogn) так что в теории быстрая может работать быстрее. Если я не напутал с оценкой сортировки слиянием
                      0
                      Между тем есть вероятность получить на быстрой сортировке O(N^2). На самом деле быстрая сортировка при прочих равных немного быстрее сортировки слиянием, за счет меньшего количестве перестановок (даже не смотря на то, что коэффициент при NlogN у быстрой сортировки не 1, а 2, если быть точнее, то там по-моему 1.39 в курсе проходила оценка). У сортировки слиянием свою плюсы… В общем между ними примерно паритет, выбор той или иной сортировки зависит от конкретных условий задачи.
                        0
                        Это да, быстрая до О(n^2) легко падает, вы правы в общем)
                          0
                          Ну как легко...) вероятность не очень высока, я бы даже сказал достаточно мала, при условии что перед сортировкой производится перемешивание входных данных.
                            0
                            Если поделится так, что в одной части 1 элемент а в другой n-1 будет квадрат, обратный порядок, например
                              0
                              ну собственно обратный порядок вроде и есть худший случай, при случайном перемешивании входных данных, вероятность такого события достаточно мала. не готов дать точную оценку вероятности.
                                0
                                Нет, обратный порядок это один из лучших случаев, особенно при выборе пивота посередине. Такой массив будет отсортирован уже после первой итерации, дальше будут только сравнения без обменов.

                                Если пивот выбирается случайным образом, то вероятность худшего случая 1/(N!), если не напутал, причем от входного массива не зависит. Т.е. зависит конечно, учитывая то, что генераторы псевдослучайны. При этом, если выбирать пивот по принципу выборки трех элементов массива, и выбора среднего из них, то вероятность соотвественно еще ниже.
                                  0
                                  Напутал с вероятностью. В массиве же два «худших» элемента, а не один. Меньший и больший. Но все равно вероятность очень и очень маленькая.
                        +1
                        На удобном для быстрой сортировки наборе — конечно. Но нельзя сранивать несравнимые вещи — тета это не то же самое, что O в среднем.
                        Также есть реализации merge, которые в лучшем случае работают за O(N) — соответствено у них нет теты.
                        Кстати я вгляделся и перестал понимать таблицы в статье — что в них вообще содержится? Потому что это точно не O — у него нет констант.
                      0
                      поправьте если я не прав, но табличку по сортировкам можно так интерпретировать. worst case — O(), avr. case — тета(), best case — омега().
                        0
                        O — ограничение работы алгоритма сверху; тета — сверху и снизу; омега — снизу. Лучший будет О, т.к в теории алгоритм может работать быстрее.
                          0
                          Не совсем понял про лучший. Что значит лучший будет О?

                          О — это худший случай, в среднем будет быстрее.
                            0
                            Я имел в виду какой алгоритм будет работать быстрее при одинаковых ограничивающих функциях g(n), но разных асимптотических оценках O(g(n)), teta(g(n)) и omega(g(n))
                      +1
                      А где же heapsort? Тоже ведь эффективный алгоритм.
                        0
                        heapsort в курсе был, но вот в сводную таблицу не попал. Посмотрел по слайдам информацию по heapsort, в худшем случае NlogN, то есть O(NlogN). Не устойчива, но не требует дополнительной памяти.

                        Видимо назревает необходимость вручную табличку переделать с добавлением сортировок.
                        +1
                        Я себе несколько лет назад приготовил небольшой конспектик по алгоритмам на основе Википедии: files.mail.ru/1APV8Y
                        Полезно, если надо освежить в памяти экзотические алгоритмы перед интервью.

                        А здесь files.mail.ru/39KWOB — более развернутый конспект (тоже на основе Википедии)
                          0
                          Хороший конспект. Возьму на заметку.
                          • НЛО прилетело и опубликовало эту надпись здесь
                              0
                              Вот нагуглил парочку:
                              1) www.algolist.net/ (у меня в Опере верстка поехала — основной тексту уехал вниз)
                              2) www.cs.auckland.ac.nz/~jmor159/PLDS210/ds_ToC.html (субъективно слегка вырвиглазная графика и цвета)
                                +1
                                http://e-maxx.ru/algo
                                Сборник сделан Ивановым Максимом — выпускником мех-мата Саратовского ГУ, серебрянным призером чемпионата мира по программированию ACM-ICPC 2011.
                              0
                              Эх, только закончили в универе первый курс по алгоритмам, как тут такая «шпоргалка»
                                0
                                Эх, только вроде закончили на хабре обсуждение ущербности Comic Sans, как тут такая шпаргалка
                                  0
                                  Перед ценными данными, проблема шрифтов блекнет)
                                  0
                                  Хочешь карму на Школьном Портале Хабре – запости старую таблицу с Википедии!
                                    0
                                    Я хотел указать на бессмысленность таких статей ввиду наличия обновляемых, редактируемых сообществом, динамических (табличку можно сортировать по разному) данных на Википедии. Т. е. если бы топики-ссылки до сих пор существовали лучше было бы просто дать ссылку, которую я запостил, и все.
                                  0
                                  Очень жаль, что закрыли материалы курса. Насколько я понял, это позиция Принстона.
                                  Вторую часть, кстати, отложили на месяц.

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                  Самое читаемое