Я беру курс вычислительной сложности и до сих пор создавал впечатление, что он не будет очень полезен для разработчика.
Возможно, я ошибаюсь, но если вы пошли по этому пути раньше, не могли бы вы привести пример того, как теория сложности помогла вам в вашей работе? Тонны благодарности.
O (1): Обычный код без петель. Просто протекает. Поиск в таблице поиска также O (1).
O (log (n)): эффективно оптимизированные алгоритмы. Пример: алгоритмы двоичного дерева и двоичный поиск. Обычно не болит. Вам повезло, если у вас есть такой алгоритм.
O (n): один цикл по данным. Hurts для очень большого n.
O (n * log (n)): алгоритм, который выполняет какую-то стратегию разделения и покорения. Болит за большие п. Типичный пример: сортировка слияния
O (n * n): вложенная петля какого-то типа. Болит даже с небольшим n. Общие с наивными матричными расчетами. Вы хотите избежать этого алгоритма, если сможете.
O (n ^ x для x > 2): злая конструкция с несколькими вложенными циклами. Болит за очень маленький n.
O (x ^ n, n! и хуже): freaky (и часто рекурсивные) алгоритмы, которые вы не хотите иметь в производственном коде, за исключением очень контролируемых случаев, для очень маленького n, и если действительно нет лучшей альтернативы, Время вычисления может взорваться с n = n + 1.
Перемещение вашего алгоритма из класса более высокой сложности может заставить ваш алгоритм летать. Вспомните преобразование Фурье, у которого есть алгоритм O (n * n), который был непригодным для использования с оборудованием 1960-х годов, за исключением редких случаев. Затем Кули и Туки сделали некоторые умные сокращения сложности, повторно используя уже рассчитанные значения. Это привело к широкому внедрению БПФ в обработку сигналов. И, в конце концов, это также объясняет, почему Стив Джобс добился успеха с iPod.
Простой пример: программисты Naive C пишут такой тип цикла:
for (int cnt=0; cnt < strlen(s) ; cnt++) {
/* some code */
}
Это алгоритм O (n * n) из-за реализации strlen(). Гнездовые петли приводят к умножению сложностей внутри большого О. O (n) внутри O (n) дает O (n * n). O (n ^ 3) внутри O (n) дает O (n ^ 4). В этом примере предварительная вычисление длины строки немедленно превратит цикл в O (n). Джоэл также написал об этом.
Однако класс сложности - это еще не все. Вы должны следить за размером n. Переработка алгоритма O (n * log (n)) для O (n) не поможет, если количество (теперь линейных) команд растет массово из-за переделки. И если в любом случае n мало, оптимизация также не даст большого взрыва.
Хотя верно, что в разработке программного обеспечения можно очень далеко продвинуться без малейшего понимания алгоритмической сложности. Я нахожу, что все время использую свои знания о сложности; хотя на данный момент это часто не осознает этого. Две вещи, которые изучают сложность, дают вам в качестве разработчика программного обеспечения способ сравнить не похожие алгоритмы, которые делают то же самое (алгоритмы сортировки являются классическим примером, но большинство людей фактически не пишет свои собственные виды). Более полезная вещь, которую он дает вам, - это способ быстро описать алгоритм.
Например, рассмотрим SQL. SQL используется каждый день очень большим количеством программистов. Если бы вы увидели следующий запрос, ваше понимание запроса сильно отличается, если вы изучили сложность.
SELECT User.*, COUNT(Order.*) OrderCount FROM User Join Order ON User.UserId = Order.UserId
Если вы изучили сложность, тогда вы поймете, что кто-то сказал, что это O (n ^ 2) для определенной СУБД. Без теории сложности человек должен был бы объяснить о сканировании таблиц и тому подобных. Если мы добавим индекс в таблицу Order
CREATE INDEX ORDER_USERID ON Order(UserId)
Тогда вышеприведенный запрос может быть O (n log n), что будет иметь огромное значение для большого DB, но для небольшого, это ничего.
Можно утверждать, что теория сложности не нужна для понимания того, как работают базы данных, и они были бы правильными, но теория сложности дает язык для размышлений и разговоров об алгоритмах, работающих с данными.
Для большинства типов программирования часть теории и доказательства могут быть не полезны сами по себе, но то, что они делают, - это попытка дать вам интуицию о возможности сразу сказать "этот алгоритм O (n ^ 2), поэтому мы не можем запустить его на этих миллионах точек данных". Даже в самой элементарной обработке больших объемов данных вы столкнетесь с этим.
Мысль о быстрой теории сложности была важна для меня в обработке бизнес-данных, ГИС, графическом программировании и алгоритмах понимания в целом. Это один из самых полезных уроков, которые вы можете получить из исследований CS по сравнению с тем, что вы обычно изучали в противном случае.
Компьютеры не умны, они будут делать то, что вы им наставляете. Компиляторы могут немного оптимизировать код для вас, но они не могут оптимизировать алгоритмы. Человеческий мозг работает по-разному, поэтому вам нужно понять Большого О. Рассмотрим расчёт чисел Фибоначчи. Мы все знаем, что F (n) = F (n-1) + F (n-2), и начиная с 1,1 вы можете легко вычислить следующие числа без особых усилий в линейном времени. Но если вы скажете компьютеру вычислить его с помощью этой формулы (рекурсивно), она не будет линейной (по крайней мере, на императивных языках). Так или иначе, наш оптимизированный мозг алгоритм, но компилятор не может этого сделать. Таким образом, вы должны работать в алгоритме, чтобы сделать его лучше.
И тогда вам нужна тренировка, чтобы определить мозговые оптимизации, которые выглядят настолько очевидными, чтобы увидеть, когда код может быть неэффективным, знать шаблоны для плохих и хороших алгоритмов (с точки зрения сложности вычислений) и так далее. В основном, эти курсы служат для нескольких вещей:
Это очень важно. Если вы не понимаете, как оценить и выяснить, как долго будут выполняться ваши алгоритмы для запуска, вы в конечном итоге напишите довольно медленный код. Я все время думаю о вычислительной сложности при написании алгоритмов. Это то, что всегда должно быть в вашем уме при программировании.
Это особенно верно во многих случаях, потому что, хотя ваше приложение может отлично работать на вашем настольном компьютере с небольшим набором тестовых данных, важно понять, как быстро ваше приложение будет реагировать, когда вы с ним живете, и есть сотни тысячи людей используют его.
Да, я часто использую нотацию Big-O, или, вернее, я использую за ней мыслительные процессы, а не сама нотация. Во многом потому, что так мало разработчиков в организации (-ах) я часто понимаю. Я не хочу быть неуважением к этим людям, но, по моему опыту, знание этого материала - одна из тех вещей, которые "сортируют мужчин от мальчиков".
Интересно, является ли это одним из тех вопросов, которые могут принимать только ответы "да"? Мне кажется, что набор людей, которые понимают вычислительную сложность, примерно эквивалентен набору людей, которые считают это важным. Таким образом, любой, кто может ответить, возможно, не понимает вопроса и, следовательно, переходит к следующему вопросу, а не к паузе, чтобы ответить. Просто мысль; -)
Есть моменты, когда вы столкнетесь с проблемами, которые требуют думать о них. Существует много реальных проблем, требующих манипулирования большим набором данных...
Примеры:
Прохождение курса по вычислительной сложности поможет вам в анализе и выборе/создании алгоритмов, эффективных для таких сценариев.
Поверьте, что-то столь же простое, как уменьшение коэффициента, скажем, от T (3n) до T (2n), может сделать ОГРОМНЫЕ различия, когда "n" измеряется в днях, если не месяцев.
Здесь есть много хороших советов, и я уверен, что большинство программистов время от времени использовали свои знания о сложности.
Однако я должен сказать, что понимание вычислительной сложности имеет чрезвычайно важное значение в области игр! Да, вы это слышали, что "бесполезный" материал - это то, о чем идет речь.
Я бы поспорил, что очень немногие профессионалы, вероятно, заботятся о Big-O, а также о программистах.
Я регулярно использую вычисления сложности, в основном потому, что я работаю в геопространственной области с очень большими наборами данных, например. процессы, связанные с миллионами, а иногда и миллиардами декартовых координат. Как только вы начнете сталкиваться с многомерными проблемами, сложность может быть реальной проблемой, так как жадные алгоритмы, которые будут O (n) в одном измерении, внезапно переходят в O (n ^ 3) в трех измерениях и не требуют большого количества данных для создать серьезное узкое место. Как я уже упоминал в подобном сообщении, вы также видите, что примечание большого O становится громоздким, когда вы начинаете общаться с группами сложных объектов разного размера. Порядок сложностей также может быть очень зависимым от данных, при этом типичные случаи выполняются намного лучше, чем общие случаи для хорошо разработанных алгоритмов ad hoc.
Также стоит проверить ваши алгоритмы под профилировщиком, чтобы убедиться, что то, что вы разработали, - это то, что вы достигли. Я нахожу, что большинство узких мест разрешено намного лучше с настройкой алгоритма, чем улучшенная скорость процессора по всем очевидным причинам.
Для более подробного ознакомления с общими алгоритмами и их сложностями я нашел Sedgewicks work как информативным, так и доступным. Для пространственных алгоритмов отличная книга O'Rourkes по вычислительной геометрии.
В вашей обычной жизни, а не рядом с компьютером, вы должны применять концепции сложности и параллельной обработки. Это позволит вам быть более эффективными. Когерентность кеша. Такого рода вещи.
Хорошим примером может быть, когда ваш босс попросит вас сделать какую-то программу, и вы можете продемонстрировать с помощью теории сложности вычислений, что то, что ваш босс просит вас сделать, невозможно.
Да, мои знания алгоритмов сортировки пригодились в один прекрасный день, когда мне пришлось сортировать стопку студенческих экзаменов. Я использовал сортировку слияния (но не quicksort или heapsort). При программировании я использую любую процедуру сортировки, предлагаемую библиотекой. (еще не пришлось сортировать действительно большой объем данных.)
Я все время использую теорию сложности в программировании, в основном, при определении того, какие структуры данных использовать, но также при определении того, нужно ли сортировать вещи и для многих других решений.
' да' и нет '
да) Я часто использую большую O-нотацию при разработке и реализации алгоритмов. Например. когда вы должны обрабатывать 10 ^ 3 элемента, а сложность первого алгоритма - O (n log (n)), а вторая O (n ^ 3), вы просто можете сказать, что первый алгоритм является почти реальным временем, а второй требует значительные расчеты.
Иногда могут быть полезны знания о классы сложности NP. Это может помочь вам понять, что вы можете перестать думать о том, как изобретать эффективный алгоритм, когда какая-то NP-полная проблема может быть сведена к проблеме, о которой вы думаете.
no) То, что я описал выше, является небольшой частью теории сложностей. В результате трудно сказать, что я использую его, я использую его второстепенную часть.
Я должен признать, что существует много проектов разработки программного обеспечения, которые не затрагивают разработку алгоритмов или их использование сложным способом. В таких случаях теория сложности бесполезна. Обычные пользователи алгоритмов часто работают с использованием слов "fast" и "slow", "x seconds" и т.д.
@Martin: Не могли бы вы рассказать о процессах мышления?
он может быть не столь явным, как сидеть и разрабатывать нотацию Big-O для решения, но он создает понимание проблемы - и это направляет вас на поиск более эффективного ответа и от проблем в подходах вы можете взять. например O (n * n) по сравнению с чем-то более быстрым, например. поиск слов, хранящихся в списке, в сравнении с хранимым в trie (надуманный пример)
Я нахожу, что это имеет значение для того, какие структуры данных я буду использовать, и как я буду работать с большим количеством записей.