Вы используете Большую-O оценку сложности в 'реальном мире'?

Вы имеете в виду как это?

void foo ( int i ) {
    if ( i < 0 ) return; // do nothing
    // do something
}
16
задан 2 revs, 2 users 100% 7 June 2012 в 18:47
поделиться

10 ответов

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

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

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

19
ответ дан 30 November 2019 в 15:20
поделиться

Нет ненужного n-квадрата

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

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

11
ответ дан 30 November 2019 в 15:20
поделиться

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

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

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

8
ответ дан 30 November 2019 в 15:20
поделиться

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

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

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

Итак, по моему опыту, профилирование полезно ТОЛЬКО ПОСЛЕ того, как будет использован правильный класс алгоритмов.

6
ответ дан 30 November 2019 в 15:20
поделиться

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

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

5
ответ дан 30 November 2019 в 15:20
поделиться

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

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

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

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

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

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

2
ответ дан 30 November 2019 в 15:20
поделиться

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

Моя точка зрения на всю проблему такова - (может быть, неверно ... но это только мое мнение).

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

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

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

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

2
ответ дан 30 November 2019 в 15:20
поделиться

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

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

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

3
ответ дан 30 November 2019 в 15:20
поделиться

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

2
ответ дан 30 November 2019 в 15:20
поделиться

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

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

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

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

1
ответ дан 30 November 2019 в 15:20
поделиться
Другие вопросы по тегам:

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