У меня был болезненный опыт в классах "Анализ алгоритмов" еще в колледже, но он недавно нашел в нем необходимость в реальном мире. - В любом случае, я ищу простой, но эффективный курс крушения. Любые идеи?
Связанный Sidenote: Конечно, было бы неплохо, если бы было "Руководство по анализу алгоритмов для мультфильмов", которое преподавал Дилберт.
ОБНОВЛЕНИЕ: Очень похожий вопрос можно найти по адресу: Как начать работу с ALGORITHMS?
Есть много хороших книг по этому вопросу. Мне нравится Введение в анализ алгоритмов. Также проверьте курс алгоритмов на MIT OpenCourseWare (используя CLRS как текст курса). Он немного глубокий, но его онлайн-доступ позволяет вам идти в своем собственном темпе.
Несколько других книг, которые я недавно начал читать, Алгоритмы в двух словах и Руководство по разработке алгоритмов. Они используют более легкий подход, чем большинство книг алгоритмов. Вместо тяжелых математических и формальных доказательств эти книги дают вам реалистичные заявления о проблемах и показывают шаги, предпринятые для уточнения алгоритма. Они также показывают, как оценить и измерить сложность решения. Я бы очень рекомендовал любую книгу.
Аналогично, UC Berkeley имеет множество подкастов, которые могут оказаться полезными.
Университет Google Code предлагает страницу по алгоритмам, который указывает на некоторые слайды, предлагаемые Stanford и Princeton.
Эрик Öjebo опубликовал отличный ответ на почти идентичный вопрос, спросил вскоре после вашего.
Цитируя свой ответ:
В MIT есть курс по алгоритмам в Open Courseware Program с лекциями видео, аудио и PDF.
Существует также онлайн-курс, также с видео-лекциями, в ArsDigita University.
В Университет Флориды есть курс Структуры данных и Алгоритмы на Java, и так же, как выше, у него есть видео-лекции, доступные онлайн.
В freescienceonline.blogspot.com вы можете найти множество видео-лекций по алгоритмам, а также множество других интересных видеороликов.
Мне нравится Введение в алгоритмы от Cormen, Leiserson, Rivest и Stein. Это немного тяжело, но я нашел, что это приличный справочный текст.
Вы не говорите много о оставшейся части фона. Для прямого анализа алгоритмов, методы, по которым вы оцениваете алгоритм, чтобы найти его порядок статистики и поведения, Если вам нравится математика в целом - скажем, у вас было два года исчисления или хороший курс абстрактной алгебры - тогда вы не можете сделать гораздо лучше, чем читать Knuth Volume One.
Обычный курс "Анализ алгоритмов" также является курсом структуры данных, поэтому текст структур данных может быть лучше, если вам также нужно узнать о списках, деревьях и т.д. Мой любимый в аспирантуре был Ахо, Хопкрофт и Ульман.
Мне нравится Cormen как ссылка; он также служит замечательным дверным замком, для выполнения больших нехороших ошибок, для зажима небольших клеящих суставов (гладкая обложка высвобождает большинство деревянных клеев) и в качестве конечной книги, потому что она содержит букранд на месте. Не рекомендовал бы это как вводный текст.
Существует простой ярлык для понимания производительности алгоритмов поиска и сортировки, если это то, что вы ищете.
Сначала сортировка - это в основном повторный поиск. Для каждого из N элементов вы ищите, куда их вставить в список, а затем вставляете их, поэтому он принимает N раз большую-O процедуры поиска.
Чтобы понять большой поиск O, простой способ состоит в том, чтобы думать о нем как о серии решений (обычно двоичных) с определенной вероятностью принятия каждой ветки.
Предположим, что ваша таблица имеет N = 1024 записи. Это означает, что для индексации таблицы требуется 10 бит, потому что log (1024) = 10 (база 2). Поиск - это процесс изучения этих 10 бит.
Если точка решения имеет примерно равную вероятность перехода в любом направлении, то она имеет энтропию -0,5 log (0,5) - 0,5 log (0,5) (base 2), которая равна 1 бит, поэтому она изучает 1 бит информации по каждому решению. Вуаля! Он принимает примерно 10 решений или log (N). Таким образом, сортировка O (N log (N)). Все алгоритмы сортировки NlogN основаны на бинарных решениях, имеющих примерно одинаково вероятные результаты.
Предположим, вы выполняете линейный поиск (как в сортировке пузырьков). По первому решению шанс быть прав - 1/1024 против 1023/1024. Энтропия составляет 1/1024 * log (1024/1) + 1023/1024 * log (1024/1023) или примерно 10/1024 + 0 (т.е. Около 0,01). Итак, первое решение вы узнаете только о 0,01 бит, потому что результаты настолько искажены. Вот почему линейный поиск неэффективен. Он принимает порядок N операций, поэтому сортировка принимает O (N * N).
(Помимо этого: линейный поиск фактически экспоненциальный. Если вы определяете информационное содержимое проблемы как n = log (N), тогда линейный поиск выполняет шаги O (2 ^ n). Поэтому такие вещи, как неуправляемый поиск игрового дерева экспоненциальны по числу ходов.)
С другой стороны, предположим, что вместо принятия двоичных решений вы индексируете. Вы берете некоторые или все биты слова, которое вы ищете, и используйте их как индекс в массиве, где вы предварительно сохранили ответы. Если эта операция индексирования имеет 1024 одинаково вероятных результата, то она изучает 10 бит, поэтому для получения ответа требуется всего одна операция. Это основная идея хэш-кодирования. Если ваша хеш-функция происходит, чтобы сохранить порядок, ее можно использовать для создания алгоритма сортировки O (N).
Есть причудливые способы анализа алгоритмов, и, возможно, то, что вам нужно, но глядя на них как на обучающие бит информации, составляет 99% моих потребностей.
Самый полезный инструмент, который я использовал для алгоритмов, Введение в алгоритмы.
Это единственный лучший ресурс, который я знаю для алгоритмов. Он охватывает очень много тем на большой глубине и имеет примеры повсюду. Я все еще отношусь к нему довольно часто.
Без этой книги мой класс анализа алгоритмов был бы болью.
Большинство курсов анализа алгоритмов в университетах открыты только для студентов и аспирантов высшего уровня. Почему вы ожидаете, что эту тему легко освоить? Существуют простые алгоритмы, которые легко анализировать, и статья Википедии о нотация Big O, вероятно, достаточна, чтобы понять, как и выполнять анализ на них, но выполнение анализа по любому достаточно сложному алгоритму является нетривиальным. Книга Cormen, вероятно, является наиболее широко используемой книгой по алгоритмам, но я бы не стал рассматривать изучение алгоритма анализа из него или любой другой книги безболезненно.
Если вы предпочитаете смотреть и слушать, а не читать, я могу порекомендовать курс MIT "Введение в алгоритмы". Вы можете посмотреть его бесплатно: http://academicearth.org/courses/introduction-to-algorithms
Я нашел его очень хорошим и педагогическим, хотя у меня недостаточно знаний о математике.
Я рекомендую "Структуры данных и алгоритмы" Адама Дроздека, доступные в выпусках Java и С++.
Я участвовал в 1-дневном (9-часовом) обучении по алгоритмам около года назад. Пререк был либо диплом бакалавра в Comp Sci, либо как минимум 2 года опыта программирования. Я нашел, что обучение будет ОЧЕНЬ полезным, и особенно физические закладки, которые я получил, стоили моего времени (и денег, независимо от того, что заплатила компания). Я бы присутствовал на другой такой сессии, если бы получил шанс, даже если это было в основном то же самое. Очевидно, что многое зависит от инструктора. Наш великий - забавный и практичный и активный программист, хотя у него был значительный опыт преподавания.