Вы используете оценку сложности Big-O в "реальном мире"?

Ответ 1

Это не столько использование этого, но и более того, что вы понимаете последствия.

Есть программисты, которые не осознают последствия использования алгоритма сортировки O (N ^ 2).

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

Ответ 2

Нет необходимости в n-квадрате

По моему опыту у вас мало дискуссий об этом, потому что это не нужно обсуждать. На практике, по моему опыту, все, что когда-либо случается, - это то, что вы обнаруживаете что-то медленное и видите, что оно O (n ^ 2), когда на самом деле это может быть O (n log n) или O (n), а затем вы идете и Измени это. Там нет никакого обсуждения, кроме "того, что n-квадрат, исправьте его".

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

Ответ 3

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

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

Нижняя строка: в реальной жизни результаты профилирования обычно имеют приоритет над теоретическими границами времени выполнения.

Ответ 4

Я все время. Когда вам приходится иметь дело с "большими" номерами, как правило, в моем случае: пользователи, строки в базе данных, коды продвижения и т.д., Вы должны знать и учитывать Big-O ваших алгоритмов.

Например, алгоритм, который генерирует случайные коды продвижения для распространения, может использоваться для генерации миллиардов кодов... Использование алгоритма O (N ^ 2) для генерации уникальных кодов означает недели процессорного времени, тогда как O (N ) означает часы.

Другим типичным примером являются запросы в коде (bad!). Люди ищут таблицу, затем выполняют запрос для каждой строки... это вызывает порядок до N ^ 2. Обычно вы можете изменить код для правильного использования SQL и получить заказы N или NlogN.

Итак, по моему опыту, профилирование полезно ТОЛЬКО ПОСЛЕ ТОГО, КАК используется правильный класс алгоритмов. Я использую профилирование, чтобы поймать плохое поведение, например, понять, почему приложение "с небольшим числом" ограничено.

Ответ 5

Ответ на мой личный опыт - Нет. Вероятно, причина в том, что я использую только простые, хорошо понятые алгоритмы и структуры данных. Их анализ сложности уже сделан и опубликован десятилетиями назад. Почему мы должны избегать фантастических алгоритмов, лучше объяснить Rob Pike здесь. Короче говоря, практикующему почти никогда не приходилось изобретать новые алгоритмы и, как следствие, почти никогда не использовать Big-O.

Ну, это не значит, что вы не должны владеть Big-O. Проект может потребовать разработки и анализа всего нового алгоритма. Для некоторых примеров в реальном мире, пожалуйста, прочитайте "военные истории" в Skiena Руководство по разработке алгоритмов.

Ответ 6

Насколько я знаю, три вложенных for -loops, вероятно, хуже одного вложенного for -loop. Другими словами, я использую его как чувство ссылки.

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

С другой стороны, если я знаю для определенного размер n, который входит в мой алгоритм, и я знаю для определенного, он будет относительно небольшим (скажем, менее 100 элементов), я могу взять наиболее разборчивый (мне нравится знать, что мой код делает даже через месяц после его написания). В конце концов, разница между исполнением 100 ^ 2 и 100 ^ 3 едва ли заметна пользователем с сегодняшними компьютерами (пока не доказано иначе).

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

Ответ 7

Нет. Я не использую сложность Big-O в ситуациях реального мира.

Мой взгляд на весь вопрос в этом - (может быть, неправильный.. но его просто мой подход.)

В основе сложности Big-O лежит понимание того, насколько эффективен алгоритм. Если по опыту или другим способом вы понимаете алгоритмы, с которыми имеете дело, и можете использовать правильный алгоритм в нужном месте, то все, что имеет значение.

Если вы знаете этот материал Big-O и можете использовать его правильно, хорошо и хорошо.

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

Если вы этого не знаете, это плохо.

Ответ 8

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

Ответ 9

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

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

Я, как правило, размышляю, когда мне приходится выполнять много операций с списками. Я делаю ненужные вещи сложности O(n^2), которые могли быть выполнены в линейном времени? Сколько проходов я делаю над списком? Это не то, что вам нужно для формального анализа, но без знания нотации с большим О, сделать намного сложнее сделать точно.

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

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

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

Ответ 10

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

Во время разработки вы часто чувствуете, что это "достаточно хорошо". Eh, никто никогда не поставит более 100 элементов в этом массиве правильно? Затем, однажды, кто-то поместит 1000 элементов в массив (доверяйте пользователям: если код позволяет это, один из них сделает это). И этот алгоритм n ^ 2, который был достаточно хорош, теперь представляет большую проблему с производительностью.

Иногда бывает полезно наоборот: если вы знаете, что вам нужно выполнять операции n ^ 2, а сложность вашего алгоритма - n ^ 3, возможно, вы можете сделать что-то, что вы можете сделать, чтобы сделать это n ^ 2. После n ^ 2 вам придется работать с меньшими оптимизациями.

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

Ответ 11

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

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