Безболезненный 'Анализ алгоритмов' обучение? [закрытый]

Аналогично, UC, Беркли имеет бесчисленные подкасты, которые можно найти полезным.

http://webcast.berkeley.edu/course_feeds.php

предложения Google Code University страница на Алгоритмах , который указывает на некоторые слайды, предлагаемые Стэнфорд и Принстон .

Мне нравится Введение в Алгоритмы Cormen, Leiserson, Rivest и Stein. Это немного тяжело, но я нашел, что это было достойным текстом ссылки.

Erik Г–jebo отправил большой ответ к почти идентичный вопрос , спрошенный вскоре после Вашего.

Заключение в кавычки его ответа:

MIT имеет курс об алгоритмах в их , Открывают Courseware Program с видео, аудио и лекциями PDF.

• Примечания Лекции
• домашняя страница Курса

существует также онлайн-курс, также с видео лекциями, в Университет ArsDigita .

• Лекции
• домашняя страница Курса

В Флоридский университет существует Структуры данных курса и Алгоритмы в Java, и так же, как вышеупомянутое, он имеет видео лекции в наличии онлайн.

• Лекции
• домашняя страница Курса

В [1 112] freescienceonline.blogspot.com можно найти много видео лекций по алгоритмам, а также много других интересных видео.

Вы не говорите много об остатке от Вас фон. Для прямого анализ алгоритмов, в методах, которыми Вы оцениваете алгоритм для нахождения его статистики порядка и поведения, Если Вы довольны математикой в целом - говорится, что у Вас было два года исчисления или хороший курс абстрактной алгебры - тогда Вы не можете действительно сделать намного лучше, чем читать Объем Knuth Один .

обычный "Анализ Алгоритмов" курс является также курсом структур данных, таким образом, текст структур данных мог бы быть лучше, если также необходимо узнать о списках, деревьях, и т.д. Мой фаворит в аспирантуре был Aho, Hopcroft и Ullman.

мне нравится Cormen как ссылка; это также служит замечательной дверной пружиной для выполнения больших неприглядных ошибок, для фиксации маленьких клеевых соединений (гладкое покрытие выпускает большую часть древесного клея), и как книга конца, потому что это фиксирует держатель для книг. Не рекомендовал бы это как вводный текст.

Существует простой ярлык на понимание выполнения поиска и сортировки алгоритмов, если, именно это Вы ищете.

Первый, сортировка в основном повторяется поиск. Для каждого из объектов N Вы ищете, где вставить его в список и затем вставку его, таким образом, он берет временам N большую-O из поисковой процедуры.

Для понимания большой-O из поиска простой путь состоит в том, чтобы думать о нем как о ряде решений (обычно двоичный файл) с определенной вероятностью взятия каждого ответвления.

предположим Ваша таблица имеет N = 1 024 записи. Это означает, что требуется 10 битов для индексации таблицы, потому что журнал (1024) = 10 (базируются 2). Поиск является процессом изучения тех 10 битов.

, Если момент принятия решения имеет примерно равную вероятность движения так или иначе, то это имеет энтропию-0.5 журналов (0.5) - 0,5 журнала (0.5) (базируются 2), который составляет 1 бит, таким образом, это изучает 1 бит информации о каждом решении. Вуаля! Это принимает примерно 10 решений или журнал (N). Таким образом, сортировка является O (N журнал (N)). Все NlogN, сортирующие алгоритмы, основаны на выборах из двух альтернатив, имеющих примерно, одинаково вероятно, результаты.

предположим Вы делаете линейный поиск (как в пузырьковой сортировке). На первом решении шанс того, чтобы быть правильным является 1/1024 по сравнению с 1023/1024. Энтропия является 1/1024 * журнал (1024/1) + 1023/1024 * журнал (1024/1023) или примерно 10/1024 + 0 (т.е. приблизительно.01). Таким образом на первом решении Вы только изучаете приблизительно.01 бит, потому что результаты так скашиваются. Именно поэтому линейный поиск неэффективен. Это берет порядок операций N, таким образом сортирование берет O (N*N).

(В стороне: линейный поиск на самом деле экспоненциален. Если Вы определяете информационное содержание проблемы как n = журнал (N), то линейный поиск берет O (2^n) шаги. Вот почему вещи как неведомый игровой поиск по дереву экспоненциальны в количестве перемещений.)

, С другой стороны, предположите вместо того, чтобы принять решения из двух альтернатив, Вы индексируете. Вы берете некоторых или все биты слова, которое Вы ищете и используете их в качестве индекса в массив, где Вы предварительно сохранили ответы. Если та операция индексации имеет 1 024 одинаково вероятных результата, то она изучает 10 битов, таким образом, только требуется примерно 1 операция для получения ответа. Это - основная идея позади хэширования. Если Ваша хеш-функция, оказывается, сохраняет порядок, она может использоваться для создания O (N) сортировкой алгоритма.

существуют необычные способы проанализировать алгоритмы, и возможно это - то, в чем Вы нуждаетесь, но рассмотрение их как изучение битов информации обслуживает 99% моих потребностей.

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

Это - единственный лучший ресурс, о котором я знаю для алгоритмов. Это затрагивает столько тем в хорошей глубине и имеет примеры повсюду. Я все еще обращаюсь к нему вполне часто.

Без той книги мой аналитический класс алгоритмов был бы болью.

Большинство аналитических курсов алгоритма в Университетах только открыто для верхних студентов уровня и аспирантов. Почему Вы ожидали бы, что эта тема будет легка учиться? Существуют алгоритмы, которые просты проанализировать и статья Wikipedia о , Большая нотация O, вероятно, соответствует, чтобы понять, как и выполняют анализ их, но выполнение анализа любого довольно сложного алгоритма нетривиально. Книга Cormen является, вероятно, наиболее широко подержанной книгой по алгоритмам, но я не считал бы изучение анализа алгоритма от нее или любой другой книги безболезненным.