Хороший текст на сложности алгоритма

Question

Где я должен искать хороший вступительный текст в сложности алгоритма? До сих пор у меня был класс алгоритмов и несколько языковых классов, но ничего с теоретической основой. Я получаю всю сложность, но иногда мне трудно различать O (1) и O (n), плюс есть целая нотация и все это, основное объяснение p = np и простых алгоритмов, трактативность. Я хочу текст, который охватывает все это, и это не требует тяжелого математического фона или чего -то, что можно прочитать.

LE: Я все еще в старшей школе, а не в университете, и под тяжелым математическим фоном я имею в виду что -то, возможно, не очень высокое выше исчисления и линейной алгебры (это не то, что я не могу этого понять, это тот факт, что, например, изучение серии Тейлора Без исчисления я немного натянут; это то, что я имел в виду под математически тяжелым. Что -то, в котором математика с нормальным количеством усилий может быть понято). И, простите, если я ошибаюсь, но теоретически, класс, в котором они преподают методы дизайна алгоритма, и фактические алгоритмы должны называться классом «алгоритмы», не так ли? С точки зрения моего нынешнего понимания, бесконечных серий, ограничений и интегралов, которые я знаю (большинство книг сложности, на которые я взглянул, казалось, использовали эти концепции), но вы потеряли меня во время быстрого преобразования Фурье.

Answer 1

Это мое очень личное мнение, что книга Джон Кляйнберг и Эва Тардос является лучшей книгой для изучения проектирования и анализа эффективных алгоритмов. Это может быть не так всеобъемлющее, как Cormen et al. Но это отличный учебник. Позвольте мне указать, почему я думаю, что эта книга может соответствовать вашим интересам

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

Вы также должны заметить, что в www есть много бесплатных материалов. Большой конспект лекций предоставляются Джеффом Эриксоном. И вы даже можете посмотреть весь класс MIT на «Введение в алгоритмы» Преподавал Чарльз Лейзерсон и Эрик Д. Демейн. Прикольная штука!

Answer 2

Вы, безусловно, можете сделать ставку на знаменитую книгу Cormen et al. «Введение в алгоритмы». Прежде всего, довольно сложно понять книгу, если у вас нет звуковой математической базы. Но для легкого понимания вы можете пропустить эти математические доказательства (не рекомендуется). Также вы можете пойти на Руководство по дизайну алгоритма.

Answer 3

Вы должны взглянуть на М. Сипзер "Введение в теорию вычислений«Я прочитал (и понял) эту книгу, когда учился в старшей школе, поэтому я думаю, что она подходит для вас.

Хотя это довольно формально, все также объясняется на простом английском языке. Он также имеет небольшое представление о методах доказательств в начале.

---

Примечание. Если вы хотите сделать CS на серьезном уровне (например, исследования), вам нужен твердый Фон в математике. Там нет короткого разреза. Посмотрите на IE Graham, Knuth и Patashnik's Бетонная математика.