Что такое Большая нотация O? Вы используете его? [дубликат]

В Java все находится в форме класса.

Если вы хотите использовать любой объект, тогда у вас есть две фазы:

  1. Объявить
  2. Инициализация

Пример:

  • Объявление: Object a;
  • Инициализация: a=new Object();

То же самое для концепции массива

  • Объявление: Item i[]=new Item[5];
  • Инициализация: i[0]=new Item();

Если вы не дают секцию инициализации, тогда возникает NullpointerException.

29
задан Community 23 May 2017 в 12:10
поделиться

12 ответов

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

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

Однако, если у Вас есть два совершенно различных алгоритма и один (A), O(n^2), и другой один (B) O(log n), не сказано, что A медленнее, чем B. На самом деле, с 100 объектами, A могло бы быть в десять раз быстрее, чем B. Это только говорит, что с 200 объектами, A станет медленнее фактором n^2, и B станет медленнее фактором log n. Так, если Вы сравниваете обоих, и Вы знаете, сколько время A берет для обработки 100 объектов, и сколько времени B потребности в тех же 100 объектах, и A быстрее, чем [1 115], можно вычислить в том, что количество объектов B настигнет A в скорости (как скорость [1 118] уменьшения намного медленнее, чем то [1 119], это настигнет A раньше или later—, это наверняка).

32
ответ дан Gabriel Nahmias 28 November 2019 в 01:20
поделиться

Очень похожий вопрос уже задали в Большой-O для Восьми лет? . Надо надеяться, ответы там ответят на Ваш вопрос, хотя у задающего вопрос там было немного математического знания обо всем этом, которое Вы не можете иметь, так разъяснитесь, нужно ли Вам более полное объяснение.

4
ответ дан Community 28 November 2019 в 01:20
поделиться

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

Например (на Java):

/** Takes an array of strings and concatenates them
  * This is a silly way of doing things but it gets the 
  * point across hopefully
  * @param strings the array of strings to concatenate
  * @returns a string that is a result of the concatenation of all the strings
  *          in the array
  */
public static String badConcat(String[] Strings){
    String totalString = "";
    for(String s : strings) {
        for(int i = 0; i < s.length(); i++){
            totalString += s.charAt(i);
        }
    }
    return totalString;
}

Теперь подумайте, что это на самом деле делает. Он проходит через все символы ввода и складывает их вместе. Это кажется простым. Проблема в том, что String является неизменной . Поэтому каждый раз, когда вы добавляете букву в строку, вы должны создавать новую строку. Для этого вам нужно скопировать значения из старой строки в новую строку и добавить новый символ.

Это означает, что вы будете копировать первую букву n раз, где n - количество символов на входе. Вы будете копировать символ n-1 раз, так что всего будет (n-1)(n/2) копий.

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

Использование чего-то вроде StringBuilder будет происходить по линии O (nLog (n)). Если вы рассчитаете количество символов в начале и установите емкость StringBuilder, вы можете получить значение O(n).

Таким образом, если бы у нас было 1000 символов ввода, первый пример выполнял бы примерно миллион операций, StringBuilder выполнял бы 10 000, а StringBuilder с setCapacity выполняли бы 1000 операций, чтобы сделать то же самое. Это приблизительная оценка, но запись O(n) о порядках величин, а не точное время выполнения.

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

8
ответ дан liamzebedee 28 November 2019 в 01:20
поделиться

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

1) Это порядок измерения эффективности алгоритма при работе со структурой данных.

2) Действия типа «добавить» / «сортировать» / «удалить» могут занимать разное время с разными структурами данных (и алгоритмами), например, «добавить» и «найти» - это O (1) для хэш-карты , но O (log n) для двоичного дерева. Сортировка - это O (nlog n) для быстрой сортировки, но O (n ^ 2) для BubbleSort при работе с простым массивом.

3) Расчеты можно выполнить, рассматривая глубину цикла вашего алгоритма в целом. Без циклов, O (1), циклы, повторяющиеся по всему набору (даже если они вспыхивают в некоторой точке) O (n). Если цикл делит пространство поиска пополам на каждую итерацию? O (журнал N). Возьмите самое высокое O () для последовательности циклов и умножьте O (), когда вы вкладываете циклы.

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

3
ответ дан 2 revs 28 November 2019 в 01:20
поделиться

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

Оказывается, что это очень полезная идея в компьютерных науках и, в частности, в анализе алгоритмов, потому что нас часто точно интересуют темпы роста функций, которые представляют, например, время, затрачиваемое двумя разными алгоритмами. Грубо говоря, мы можем определить, что алгоритм с временем выполнения t1 (n) более эффективен, чем алгоритм с временем выполнения t2 (n), если t1 = O (t2) для достаточно большого n, который обычно является «размером» проблема - как длина массива или количество узлов в графе или что-то еще.

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

Тем не менее, это означает, что нотация big-O менее полезна для малых n, потому что медленные растущие термины, о которых мы забыли, все еще достаточно значительны, чтобы влиять на время выполнения.

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

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

3
ответ дан HenryR 28 November 2019 в 01:20
поделиться

«Интуиция» за Big-O

Представьте себе «конкуренцию» между двумя функциями по x, когда x приближается к бесконечности: f (x) и g (x).

Теперь, если с некоторой точки (некоторый x) одна функция всегда имеет более высокое значение, чем другая, то давайте назовем эту функцию «быстрее», чем другую.

Так, например, если для каждого x> 100 вы видите, что f (x)> g (x), то f (x) «быстрее», чем g (x).

В этом случае мы бы сказали, что g (x) = O (f (x)). f (x) представляет собой своего рода «ограничение скорости» для g (x), так как в конечном итоге оно проходит его и оставляет его навсегда.

Это не совсем определение нотации big-O , в которой также говорится, что f (x) должно быть больше, чем C * g (x) для некоторой константы C (которая просто другой способ сказать, что вы не можете помочь g (x) выиграть соревнование, умножив его на постоянный коэффициент - f (x) всегда победит в конце). Формальное определение также использует абсолютные значения. Но я надеюсь, что мне удалось сделать его интуитивно понятным.

3
ответ дан Assaf Lavie 28 November 2019 в 01:20
поделиться

Это может также быть достойно рассмотрения, что сложность многих алгоритмов основана больше чем на одной переменной, особенно в многомерных проблемах. Например, я недавно должен был записать алгоритм для следующего. Учитывая ряд n точки и m полигоны, извлекают все точки, которые лежат в любом из полигонов. Сложность базируется приблизительно две известных переменные, n и m, и неизвестные из сколько точек находятся в каждом полигоне. Большая нотация O здесь вполне немного более включена, чем O (f (n)) или даже O (f (n) + g (m)). Большой O хорош, когда Вы имеете дело с большими количествами однородных объектов, но не ожидаете, что это всегда будет иметь место.

также стоит отметить, что фактическое количество повторений по данным часто зависит от данных. Quicksort обычно быстр, но дайте предварительно отсортированные данные, и это замедляется. Мои точки и полигоны alogorithm закончились довольно быстро, близко к O (n + (m журнал (m)), на основе предварительных знаний того, как данные, вероятно, будут организованы и относительные размеры n и m. Это падало бы плохо на случайным образом организованных данных различных относительных размеров.

вещь финала А рассмотреть состоит в том, что часто существует прямой компромисс между скоростью алгоритма и суммой пространства, которое это использует. дыра Голубя, сортирующая , является довольно хорошим примером этого. При возвращении к моим точкам и полигонам, позволяет, говорят, что все мои полигоны были просты и быстры для рисования, и я мог потянуть их заполненный на экране, сказать в синем в фиксированном количестве времени каждый. Таким образом, если бы я тяну свои m полигоны на черном экране, он взял бы O (m) время. Чтобы проверить, была ли какая-либо из моих точек n в полигоне, я просто проверяю, является ли пиксель в той точке зеленым или черным. Таким образом, проверка является O (n), и общий анализ является O (m + n). Оборотная сторона, конечно - то, что мне нужно близкое безграничное хранение, если я имею дело с координатами реального мира с точностью миллиметра....... ho гул.

2
ответ дан SmacL 28 November 2019 в 01:20
поделиться

Из Википедии .....

Обозначение Big O полезно при анализе эффективности алгоритмов. Например, время (или количество шагов), необходимое для решения задачи размера n, может быть найдено равным T (n) = 4n² - 2n + 2.

По мере того, как n становится большим, термин n² станет доминирующим, так что всеми другими терминами можно пренебречь - например, когда n = 500, термин 4n² в 1000 раз больше, чем член 2n. Игнорирование последнего будет незначительно влиять на значение выражения для большинства целей.

Очевидно, я никогда не использовал его ..

1
ответ дан Brian G 28 November 2019 в 01:20
поделиться

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

Хорошим примером является динамическая таблица, которая в основном представляет собой массив, который расширяется по мере добавления к нему элементов. Наивная реализация будет увеличивать размер массива на 1 для каждого добавленного элемента, а это означает, что все элементы необходимо копировать каждый раз, когда добавляется новый. Это приведет к алгоритму O (n 2 ) , если вы будете объединять серии массивов с помощью этого метода. Альтернатива - удваивать емкость массива каждый раз, когда вам нужно больше памяти. Даже если добавление иногда является операцией O (n) , вам нужно будет только скопировать элементы O (n) для каждого добавленного элемента n , поэтому операция в среднем составляет O (1) . Вот как реализованы такие вещи, как StringBuilder или std :: vector .

2
ответ дан Jay Conrod 28 November 2019 в 01:20
поделиться

Он говорит, сколько итераций алгоритм имеет в худшем случае.

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

Допустим, в списке есть n элементов. В худшем случае вы берете n итераций. В уведомлении Большой О это O (n).

Фактически это говорит о том, насколько эффективен алгоритм.

0
ответ дан Ikke 28 November 2019 в 01:20
поделиться

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

1
ответ дан Bernard 28 November 2019 в 01:20
поделиться

What is Big O notation?

Big O notation is a method of expressing the relationship between many steps an algorithm will require related to the size of the input data. This is referred to as the algorithmic complexity. For example sorting a list of size N using Bubble Sort takes O(N^2) steps.

Do I use Big O notation?

I do use Big O notation on occasion to convey algorithmic complexity to fellow programmers. I use the underlying theory (e.g. Big O analysis techniques) all of the time when I think about what algorithms to use.

Concrete Examples?

I have used the theory of complexity analysis to create algorithms for efficient stack data structures which require no memory reallocation, and which support average time of O(N) for indexing. I have used Big O notation to explain the algorithm to other people. I have also used complexity analysis to understand when linear time sorting O(N) is possible.

2
ответ дан 28 November 2019 в 01:20
поделиться
Другие вопросы по тегам:

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