Применяли ли вы теорию вычислительной сложности в реальной жизни?

Question

Я прохожу курс по вычислительной сложности, и до сих пор у меня сложилось впечатление, что разработчику это не сильно поможет.

Возможно, я ошибаюсь, но если вы уже шли по этому пути раньше, не могли бы вы, пожалуйста, привести пример того, как теория сложности помогла вам в вашей работе?Огромное спасибо.

Answer 1

O(1):Простой код без циклов.Просто течет сквозь него.Поисковые запросы в таблице подстановки тоже равны O(1).

O(логарифм(n)):эффективно оптимизированные алгоритмы.Пример:алгоритмы бинарного дерева и бинарный поиск.Обычно это не причиняет боли.Вам повезло, если у вас есть такой алгоритм под рукой.

O (n):один цикл обработки данных.Болит при очень большом n.

O(n*логарифм (n)):алгоритм, который использует своего рода стратегию "разделяй и властвуй".Болит за большой n.Типичный пример:сортировка слиянием

O (n*n):какой-то вложенный цикл.Болит даже при небольших ушибах.Распространено при наивных матричных вычислениях.Вы хотите избежать такого алгоритма, если сможете.

O(n ^ x для x>2):злая конструкция с несколькими вложенными циклами.Болит за очень маленькую п.

O(x^n, n!и еще хуже):причудливые (и часто рекурсивные) алгоритмы, которые вы не хотите иметь в производственном коде, за исключением очень контролируемых случаев, для очень маленьких n и если действительно нет лучшей альтернативы.Время вычисления может увеличиться при n = n + 1.

Понижение вашего алгоритма с более высокого класса сложности может привести к тому, что он будет работать быстрее.Подумайте о преобразовании Фурье, которое имеет алгоритм O (n * n), который был непригоден для аппаратного обеспечения 1960-х годов, за исключением редких случаев.Затем Кули и Тьюки сделали несколько хитроумных сокращений сложности, повторно используя уже вычисленные значения.Это привело к широкому внедрению БПФ в обработку сигналов.И, в конце концов, именно поэтому Стив Джобс сколотил состояние на iPod.

Простой пример:Наивные программисты на C пишут такой цикл:

for (int cnt=0; cnt < strlen(s) ; cnt++) {
  /* some code */
}

Это алгоритм O (n * n) из-за реализации strlen().Вложенность циклов приводит к умножению сложностей внутри big-O.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 в любом случае мало, оптимизация тоже не даст большого эффекта.

Answer 2

Хотя это правда, что можно действительно далеко продвинуться в разработке программного обеспечения без малейшего понимания алгоритмической сложности.Я обнаружил, что постоянно использую свои знания о сложности;хотя на данный момент это часто происходит, даже не осознавая этого.Две вещи, которые дает вам изучение сложности как разработчику программного обеспечения, - это способ сравнить непохожие алгоритмы, которые выполняют одно и то же (классическим примером являются алгоритмы сортировки, но большинство людей на самом деле не пишут свои собственные сортировки).Более полезная вещь, которую это дает вам, - это способ быстрого описания алгоритма.

Например, рассмотрим SQL.SQL используется каждый день очень большим количеством программистов.Если бы вы увидели следующий запрос, ваше понимание запроса сильно отличалось бы, если бы вы изучали сложность.

SELECT User.*, COUNT(Order.*) OrderCount FROM User Join Order ON User.UserId = Order.UserId

Если вы изучали сложность, то вы бы поняли, если бы кто-то сказал, что это O (n ^ 2) для определенной СУБД.Без теории сложности человеку пришлось бы объяснять, что такое сканирование таблиц и тому подобное.Если мы добавим индекс в таблицу заказов

CREATE INDEX ORDER_USERID ON Order(UserId)

Тогда приведенный выше запрос мог бы быть O (n log n), что имело бы огромное значение для большой базы данных, но для маленькой это вообще ничего не значит.

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

Answer 3

Для большинства типов программной работы теоретическая часть и доказательства сами по себе могут быть бесполезны, но то, что они делают, - это пытаются дать вам интуицию, позволяющую сразу сказать "этот алгоритм равен O (n ^ 2), поэтому мы не можем запустить его на этих миллионах точек данных".Даже при самой элементарной обработке больших объемов данных вы будете сталкиваться с этим.

Быстрое мышление теория сложности была важна для меня при обработке бизнес-данных, ГИС, графическом программировании и понимании алгоритмов в целом.Это один из самых полезных уроков, которые вы можете извлечь из изучения CS, по сравнению с тем, что вы обычно изучали бы самостоятельно в противном случае.

Answer 4

Компьютеры не умны, они будут делать все, что вы им прикажете.Компиляторы могут немного оптимизировать код для вас, но они не могут оптимизировать алгоритмы.Человеческий мозг работает по-другому, и именно поэтому вам нужно понять Большую букву "О" .Рассмотрим вычисление чисел Фибоначчи.Мы все знаем, что F (n) = F (n-1) + F (n-2), и, начиная с 1,1, вы можете легко вычислить следующие числа без особых усилий за линейное время.Но если вы скажете компьютеру вычислить это с помощью этой формулы (рекурсивно), это не будет линейным (по крайней мере, в императивных языках).Каким-то образом наш мозг оптимизировал алгоритм, но компилятор не может этого сделать.Итак, вы должны работа на алгоритм чтобы сделать это лучше.

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

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

Answer 5

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

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

Answer 6

Да, я часто использую нотацию Big-O, или, скорее, я использую мыслительные процессы, стоящие за ней, а не саму нотацию.Во многом потому, что в организации (организациях) так мало разработчиков, что я часто это понимаю.Я не хочу проявить неуважение к этим людям, но, по моему опыту, знание этих вещей - одна из тех вещей, которые "отличают мужчин от мальчиков".

Интересно, это один из тех вопросов, на которые можно получить только утвердительный ответ?Меня поражает, что набор людей, которые понимают сложность вычислений, примерно эквивалентен набору людей, которые считают это важным.Таким образом, любой, кто мог бы ответить "нет", возможно, не понимает вопроса и поэтому перейдет к следующему вопросу, а не сделает паузу для ответа.Просто мысль ;-)

Answer 7

Бывают моменты времени, когда вы сталкиваетесь с проблемами, требующими обдумывания.Существует множество проблем реального мира, которые требуют манипулирования большим набором данных...

Примерами являются:

• Приложение для создания карт...например, Google Maps - как бы вы обработали данные о дорожных линиях по всему миру и нарисовали их?и вам нужно нарисовать их быстро!
• Применение в логистике...подумайте о коммивояжере на стероидах
• Интеллектуальный анализ данных...всем крупным предприятиям требуется один, как бы вы обработали базу данных, содержащую 100 таблиц и более 10 миллионов строк, и получили полезные результаты до того, как тенденции устареют?

Прохождение курса по вычислительной сложности поможет вам в анализе и выборе / создании алгоритмов, эффективных для таких сценариев.

Поверьте мне, такая простая вещь, как уменьшение коэффициента, скажем, с T (3n) до T (2n), может иметь ОГРОМНОЕ значение, когда "n" измеряется в днях, если не в месяцах.

Answer 8

Здесь есть много хороших советов, и я уверен, что большинство программистов время от времени использовали свои знания о сложности.

Однако я должен сказать, что понимание вычислительной сложности чрезвычайно важно в области Игр!Да, вы слышали, что "бесполезный" материал - это тот материал, на котором живет игровое программирование.

Я бы поспорил, что очень немногие профессионалы, вероятно, заботятся о Big-O так же сильно, как программисты игр.

Answer 9

Я регулярно использую вычисления сложности, в основном потому, что работаю в геопространственной области с очень большими наборами данных, напримерпроцессы, включающие миллионы, а иногда и миллиарды декартовых координат.Как только вы начинаете решать многомерные задачи, сложность может стать реальной проблемой, поскольку жадные алгоритмы, которые были бы O (n) в одном измерении, внезапно переходят к O (n ^ 3) в трех измерениях, и для создания серьезного узкого места не требуется много данных.Как я уже упоминал в похожий пост, вы также видите, что нотация big O становится громоздкой, когда вы начинаете иметь дело с группами сложных объектов различного размера.Порядок сложности также может сильно зависеть от данных, при этом типичные случаи выполняются намного лучше, чем общие случаи для хорошо спроектированных ad hoc алгоритмы.

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

Для получения дополнительной информации об общих алгоритмах и их сложностях я нашел Работа Седжвиков одновременно информативный и доступный.Для пространственных алгоритмов, О'Рурк книга по вычислительной геометрии превосходна.

Answer 10

В вашей обычной жизни, а не рядом с компьютером, вы должны применять концепции сложности и параллельной обработки.Это позволит вам быть более эффективными.Согласованность кэша.Что-то в этом роде.

Answer 11

Да, мои знания алгоритмов сортировки однажды пригодились, когда мне пришлось сортировать стопку студенческих экзаменов.Я использовал сортировку слиянием (но не быструю или кучную).При программировании я просто использую любую процедуру сортировки, которую предлагает библиотека.(мне еще не приходилось сортировать действительно большой объем данных.)

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

Answer 12

'ДА" и "НЕТ'

ДА) Я часто использую большая буква "О" -обозначение при разработке и внедрении алгоритмов.Например.когда вы должны обработать 10 ^ 3 элемента и сложность первого алгоритма равна O (n log (n)), а второго O (n ^ 3), вы просто можете сказать, что первый алгоритм работает почти в реальном времени, в то время как второй требует значительных вычислений.

Иногда знания о Классы сложности NP может быть полезным.Это может помочь вам осознать, что вы можете перестать думать об изобретении эффективного алгоритма, когда некоторая NP-полная задача может быть сведена к проблеме, о которой вы думаете.

НЕТ) То, что я описал выше, является небольшой частью теории сложностей.В результате трудно сказать, что я им пользуюсь, я использую незначительную его часть.

Я должен признать, что существует множество проектов по разработке программного обеспечения, которые не касаются разработки алгоритмов или их сложного использования.В таких случаях теория сложности бесполезна.Обычные пользователи алгоритмов часто оперируют словами "быстрый" и "медленный", "x секунд" и т.д.

Answer 13

@Мартин:Не могли бы вы, пожалуйста, подробнее рассказать о мыслительных процессах, стоящих за этим?

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

Я нахожу, что это имеет значение в том, какие структуры данных я выберу для использования и как я буду работать с большим количеством записей.

Answer 14

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