Вопрос по complexity-theory, theory – Применяли ли вы теорию вычислительной сложности в реальной жизни?

25

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

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

Ваш Ответ

14   ответов
51

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

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

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

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

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

O (n ^ x для x & gt; 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).Джоэл также написал об этом.

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

1

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

Примеры:

  • Maps application... like Google Maps - how would you process the road line data worldwide and draw them? and you need to draw them fast!
  • Logistics application... think traveling sales man on steroids
  • Data mining... all big enterprises requires one, how would you mine a database containing 100 tables and 10m+ rows and come up with a useful results before the trends get outdated?

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

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

0

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

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

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

1

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

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

Для получения дополнительной информации об общих алгоритмах и их сложностях я нашелСеджвикс работает и информативно, и доступно. Для пространственных алгоритмовO & APOS; Rourkes Книга по вычислительной геометрии отлично.

0

& APOS;yes& APOS; и & apos;no& APOS;

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

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

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

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

0

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

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

2

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

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

0

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

1

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

4

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

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

  • understand executional patterns and data structures and what effect they have on the time your program needs to finish;
  • train your mind to spot potential problems in algorithm, when it could be inefficient on large data sets. Or understand the results of profiling;
  • learn well-known ways to improve algorithms by reducing their computational complexity;
  • prepare yourself to pass an interview in the cool company :)
6

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

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

10

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

Например, рассмотрим 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), что будет иметь огромное значение для большой БД, но для маленькой - вообще ничего.

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

2

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

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

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

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

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

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

Похожие вопросы