Я беру курс вычислительной сложности и до сих пор имел впечатление, что он не будет очень полезен для разработчика.Вы применили теорию сложности вычислений в реальной жизни?
Возможно, я ошибаюсь, но если вы уже прошли этот путь раньше, не могли бы вы привести пример того, как теория сложности помогла вам в вашей работе? Тонны благодарности.
O (1): Обычный код без петель. Просто протекает. Поиск в таблице поиска - O (1).
O (log (n)): эффективно оптимизированные алгоритмы. Пример: алгоритмы двоичного дерева и двоичный поиск. Обычно не болит. Вам повезло, если у вас есть такой алгоритм.
O (n): один цикл над данными. Болит за очень большие n.
O (n * log (n)): алгоритм, который выполняет какую-то стратегию разделения и завоевания. Болит за большие п. Типичный пример: merge sort
O (n * n): вложенная петля какого-то типа. Болит даже с небольшим n. Общий с наивными матричными расчетами. Вы хотите избежать такого алгоритма, если сможете.
O (n^x для x> 2): злая конструкция с несколькими вложенными петлями. Болит за очень маленький n.
O (x^n, n! И хуже): freaky (и часто рекурсивные) алгоритмы, которые вы не хотите иметь в производственном коде, за исключением очень контролируемых случаев, для очень маленького n, и если действительно не лучше альтернатива. Время вычисления может взорваться при n = n + 1.
Перемещение вашего алгоритма из класса повышенной сложности может заставить ваш алгоритм летать. Вспомните преобразование Фурье, у которого есть алгоритм O (n * n), который был непригодным для использования с оборудованием 1960-х годов, за исключением редких случаев. Затем Кули и Туки сделали некоторые умные сокращения сложности, повторно используя уже рассчитанные значения. Это привело к широкому внедрению БПФ в обработку сигналов. И, в конце концов, именно поэтому Стив Джобс сделал состояние с iPod.
Простой пример: Наивные программисты 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). Joel has also written about this.
Однако класс сложности - это еще не все. Вы должны следить за размером n. Переработка алгоритма O (n * log (n)) для O (n) не поможет, если количество (теперь линейных) команд растет массово из-за переделки. И если в любом случае n мало, оптимизация тоже не даст большого взрыва.
Хорошим примером может быть, когда ваш босс просит вас сделать какую-либо программу, и вы можете продемонстрировать, используя теорию сложности вычислений, которую то, что ваш босс просит вас сделать, невозможно.
Есть моменты, когда вы столкнетесь с проблемами, требующими думать о них. Есть много реальных мировых проблем, которые требуют манипуляций с большим набором данных ...
Примеры:
Проведение курса по вычислительной сложности поможет вам в анализе и выборе/создании алгоритмов, эффективных для таких сценариев.
Поверьте мне, что так просто, как уменьшение коэффициента, скажем, от T (3n) до T (2n), может сделать ОГРОМНЫЕ различия, когда «n» измеряется в днях, если не месяцев.
Это очень важно. Если вы не понимаете, как оценить и выяснить, как долго будут выполняться ваши алгоритмы для запуска, вы в конечном итоге напишите довольно медленный код. Я все время думаю о вычислительной сложности при написании алгоритмов. Это то, что всегда должно быть в вашем уме при программировании.
Это особенно актуально во многих случаях, потому что, хотя ваше приложение может работать нормально на вашем настольном компьютере с небольшим набором тестовых данных, важно понять, как быстро ваше приложение будет реагировать, как только вы начнете жить с ним, и есть сотни из тысяч людей, использующих его.
Да, мои знания алгоритмов сортировки пригодились в один прекрасный день, когда мне пришлось сортировать стопку студенческих экзаменов. Я использовал сортировку слияния (но не quicksort или heapsort). При программировании я использую любую процедуру сортировки, предлагаемую библиотекой. (пока не пришлось сортировать действительно большой объем данных.)
Я все время использую теорию сложности в программировании, главным образом, при определении того, какие структуры данных использовать, но также и при принятии решения о том, следует ли сортировать вещи , и для многих других решений.
Для большинства типов программирования часть теории и доказательства могут быть не полезны сами по себе, но то, что они делают, пытается дать вам интуицию о возможности сразу сказать «этот алгоритм O (n^2) поэтому мы не можем запустить его на этих миллионах точек данных ». Даже в самой элементарной обработке больших объемов данных вы столкнетесь с этим.
Мысль о теории сложности была важна для меня в области обработки бизнес-данных, ГИС, графического программирования и понимания алгоритмов в целом.Это один из самых полезных уроков, которые вы можете получить в исследованиях CS по сравнению с тем, что вы обычно изучали самостоятельно.
Хотя верно, что в разработке программного обеспечения можно очень далеко продвинуться без малейшего понимания алгоритмической сложности. Я нахожу, что все время использую свои знания о сложности; хотя на данный момент это часто не осознает этого. Две вещи, которые изучают сложность, дают вам в качестве разработчика программного обеспечения способ сравнить не похожие алгоритмы, которые делают то же самое (алгоритмы сортировки являются классическим примером, но большинство людей фактически не пишет свои собственные виды). Более полезная вещь, которую он дает вам, - это способ быстро описать алгоритм.
Например, рассмотрим 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 журнал N), который будет иметь огромное значение для большой БД, но для маленькой, она ничего в все.
Можно было бы утверждать, что теория сложности не нужна, чтобы понять, как работают базы данных, и они были бы правильными, но теория сложности дает язык для размышлений и разговоров об алгоритмах, работающих с данными.
«да» и «нет»
да) Я часто использую big O-notation при разработке и реализации алгоритмов. . когда вы должны обрабатывать 10^3 элемента, а сложность первого алгоритма - O (n log (n)), а вторая O (n^3), вы просто можете сказать, что первый алгоритм является почти реальным временем, а второй требует значительные расчеты.
Иногда могут быть полезны знания о NP complexities classes. Это может помочь вам понять, что вы можете перестать думать о том, как изобретать эффективный алгоритм, когда какая-то NP-полная проблема может быть сведена к проблеме, о которой вы думаете.
no) То, что я описал выше, является небольшой частью теории сложностей. В результате трудно сказать, что я использую его, я использую второстепенную часть его.
Должен признать, что существует много проектов разработки программного обеспечения, которые не затрагивают разработку алгоритмов или их использование сложным способом. В таких случаях теория сложности бесполезна. Обычные пользователи алгоритмов часто работают с использованием слов «быстрая» и «медленная», «х секунд» и т. Д.
Компьютеры не умны, они будут делать то, что вы им поручите. Компиляторы могут немного оптимизировать код для вас, но они не могут оптимизировать алгоритмы. Человеческий мозг работает по-разному, поэтому вам нужно понять Большого О. Рассмотрим расчёт чисел Фибоначчи. Мы все знаем, что F (n) = F (n-1) + F (n-2), и начиная с 1,1 вы можете легко вычислить следующие числа без особых усилий в линейном времени. Но если вы скажете компьютеру вычислить его с помощью этой формулы (рекурсивно), она не будет линейной (по крайней мере, на императивных языках). Так или иначе, наш оптимизированный мозг алгоритм, но компилятор не может этого сделать. Итак, вы должны работать по алгоритму , чтобы сделать его лучше.
А затем вам нужна тренировка, чтобы определить мозговые оптимизации, которые выглядят настолько очевидными, чтобы увидеть, когда код может быть неэффективным, чтобы знать шаблоны для плохих и хороших алгоритмов (с точки зрения вычислительной сложности) и т. Д. В основном, эти курсы служат для нескольких вещей:
Да, я часто использую Big-O обозначение, или, вернее, я использую мыслительные процессы за ним, а не само обозначение. Во многом потому, что так мало разработчиков в организации (-ах) я часто понимаю. Я не хочу быть неуважением к этим людям, но, по моему опыту, знание этого материала - одна из тех вещей, которые «сортируют мужчин от мальчиков».
Интересно, является ли это одним из тех вопросов, которые могут принимать только ответы «да»? Мне кажется, что набор людей, которые понимают вычислительную сложность, примерно эквивалентен набору людей, которые считают это важным. Таким образом, любой, кто может ответить, возможно, не понимает вопроса и, следовательно, переходит к следующему вопросу, а не к паузе, чтобы ответить. Просто мысль ;-)
Здесь есть много хороших советов, и я уверен, что большинство программистов время от времени использовали свои знания о сложности.
Однако я должен сказать, что понимание вычислительной сложности имеет чрезвычайно важное значение в области игр! Да, вы это слышали, что «бесполезный» материал - это то, о чем идет речь.
Я бы поспорил, что очень немногие профессионалы, вероятно, заботятся о Big-O так же, как и программисты.
@Martin: Не могли бы вы подробно остановиться на мыслительных процессах за этим?
Возможно, это не так ясно, как сидеть и разрабатывать нотацию Big-O для решения, но это создает понимание проблемы - и это направляет вас на поиск более эффективного ответа и от проблем в подходы, которые вы можете предпринять. например O (n * n) по сравнению с чем-то более быстрым, например. поиск слов, хранящихся в списке, в сравнении с хранимым в trie (надуманный пример)
Я нахожу, что это имеет значение с тем, какие структуры данных я буду использовать, и как я буду работать с большим количеством записей.
Я регулярно использую вычисления сложности, в основном потому, что я работаю в геопространственной области с очень большими наборами данных, например. процессы, связанные с миллионами, а иногда и миллиардами декартовых координат. Как только вы начнете сталкиваться с многомерными проблемами, сложность может быть реальной проблемой, так как жадные алгоритмы, которые будут O (n) в одном измерении, внезапно переходят в O (n^3) в трех измерениях и не требуют большого количества данных для создать серьезное узкое место. Как я упоминал в a similar post, вы также видите, что большая нотация O становится громоздкой, когда вы начинаете общаться с группами сложных объектов разного размера. Порядок сложности также может быть очень зависимым от данных, причем типичные случаи, выполняющие намного лучшие, чем общие случаи для хорошо разработанных алгоритмов ad hoc.
Также стоит проверить ваши алгоритмы под профилировщиком, чтобы убедиться, что то, что вы разработали, - это то, что вы достигли. Я нахожу, что большинство узких мест разрешено намного лучше с настройкой алгоритма, чем улучшенная скорость процессора по всем очевидным причинам.
Для более подробного ознакомления с общими алгоритмами и их сложностями я нашел Sedgewicks work как информативным, так и доступным. Для пространственных алгоритмов O'Rourkes книга по вычислительной геометрии превосходна.
В обычной жизни, а не рядом с компьютером, вы должны применять концепции сложности и параллельной обработки.Это позволит вам быть более эффективными. Когерентность кеша. Что-то в этом роде.
Одним словом, некоторые люди пишут код, который дерьмо, но не может понять, почему это дерьмо. Обозначение Big-O может помочь помочь им понять, что наряду с обозначением, о котором они не знают, это реальный эффект замедления рабочего времени их кода, который зависит от длины n в этом случае (переменная at runtime), что они не понимают, что код начинается из crappy и становится все хуже и хуже по мере увеличения размера набора данных. – 2010-06-25 12:45:24