*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

вторник, 7 июля 2009 г.

Фундаментальные алгоритмы

После того, как я жестко облажался с самопальной сортировкой, причем облажался дважды: первый раз, когда думал, что порву по скорости STL'ный std::sort(), а второй - когда не понял, что все эти "ухищрения", как я думал, по ускорению QuickSort'а, реализованные в STL'е Visual Studio, есть ни что иное, как просто давно придуманный IntroSort.

В общем, я взял в руки:

Роберт Седжвик

Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка.



и начал освежать (а местами просто узнавать с нуля) когда-то читанное в студенчестве.

Втянулся.

Заказал вторую книгу:

Роберт Седжвик

Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах



Последние несколько лет я всегда делал основной упор на новые языки, операционные системы, организацию процесса разработки, работу над качеством и т.д. Получилось, что база как-то слегка подкосилась.

Вобщем, если вы все еще можете не думая сказать, например, чем лучше хеш-таблица по сравнению со сбалансированным (например, красно-черным) деревом, почему именно Splay-дерево удобно для реализации кеша, написать по памяти пирамидальную сортировку или привести пример NP-задачи, которая не является полной, то может фундамент все еще крепок.

2 комментария:

  1. Добрый день!

    Очень советую почитать:
    1. Кормен и Ко "Алгоритмы: построение и анализ"
    http://www.cs.dartmouth.edu/~thc/CLRS3e/
    2. Кнут и Ко "Конкретная математика"
    http://www.amazon.com/Concrete-Mathematics-Foundation-Computer-Science/dp/0201558025

    С уважением,
    -Денис

    ОтветитьУдалить
  2. Да, отличные книги. Номер один у меня уже есть, правда предыдущее, 2-е издание, а Конкретную математику я давно купил, 2-е издание.

    ОтветитьУдалить