Когда (а не как и почему) рассчитывать Big O алгоритма

Question

Мне недавно задали этот вопрос в интервью, и мне было любопытно, что думают другие.

«Когда вы должны вычислить Big O?»

Большинство сайтов / книг говорят о том, КАК рассчитывать Big O, но не в действительности, когда вам следует это делать. Я разработчик начального уровня, и у меня минимальный опыт, поэтому я не уверен, что я думаю на правильном пути. Я думаю, что у вас будет целевое Big O, к которому нужно стремиться, разработайте алгоритм, затем вычислите Big O. Затем попытайтесь реорганизовать алгоритм для эффективности.

Тогда у меня возникает вопрос: это то, что на самом деле происходит в промышленности, или я далеко?

Answer 1

«Когда вы должны вычислить Big O?»

Когда вам небезразлична Сложность времени алгоритма.

Когда яcare?

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

В частности, когда вы хотите сравнить алгоритмы !

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

Answer 2

Я предполагаю, что вы хотите спросить «когда мне следует рассчитывать сложность времени?», Просто чтобы избежать технических подробностей о Тэте, Омеге и Биг-О.

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

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

Основной целью догадки является ответ на вопрос: «Что произойдет, если я получу в 10 раз больший вклад?».Если сложность постоянна, ничего не происходит (по крайней мере, в теории).Если сложность линейная, время выполнения увеличится в 10 раз.Если сложность квадратична или больше, у вас начнутся проблемы.Вторичной целью догадки является ответ на вопрос: «Какой самый большой ввод я могу обработать?». Опять же, квадратичное значение даст вам максимум 10000. O (2 ^ n) заканчивается около 25.

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

Answer 3

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

1. Тета-нотация : используется для определения средней сложности регистра, поскольку она ограничивает функцию сверху и снизу

2. Omega-Notation : ограничивает функцию снизу.Он используется для определения сложности в лучшее время

3. Запись Big-O : Это важно, поскольку говорит о сложности в худшем случае и ограничивает функцию сверху.

Теперь я думаю, что ответ на Почему BIG-O рассчитывается в том, что, используя его, мы можем получить четкое представление о том, насколько плохим может работать наш алгоритм в качестве размераввода увеличивается.И если мы сможем оптимизировать наш алгоритм для худшего случая, то средний и лучший случай позаботятся о себе.

Answer 4

Большие O или асимптотические нотации позволяют нам анализировать время выполнения алгоритма, определяя его поведение по мере увеличения размера входных данных для алгоритма.

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

Предположим, вам нужно запросить более 1 миллиарда данных.Итак, вы написали linear search алгоритм.Так все в порядке?Как бы вы узнали?Вы будете вычислять Big-O.Это O (n) для linear search.Так что в худшем случае он выполнит 1 миллиард команд для запросаЕсли ваша машина выполняет 10 ^ 7 инструкций в секунду (предположим), то это займет 100 секунд.Итак, вы видите - вы получаете анализ времени выполнения с точки зрения роста входных данных.

Answer 5

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

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