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

Question

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

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

Answer 1

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

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

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

Answer 2

' да ' и ' нет '

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

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

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

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

Answer 3

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

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

Answer 4

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