Определение обозначения Big O

Question

Мне нужна помощь, чтобы понять / сделать Big O Notation. Я понимаю цель этого, я просто не знаю, как «определить сложность по коду».

Определить обозначение Big O для каждого из следующих

а.

n=6;
cout<<n<<endl;

б.

n=16;
for (i=0; i<n; i++)
    cout<<i<<endl;

с.

i=6;
n=23;
while (i<n) {
    cout<<i-6<<endl;
    i++;
}

д.

int a[ ] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
n=10;
for (i=0; i<n; i++)
    a[i]=a[i]*2;
for (i=9; i>=0; i--)
    cout<<a[i]<<endl;

е.

sum=0;
n=6;
k=pow(2,n);
for (i=0;i<k;i++)
    sum=sum+k;

Answer 1

Big O указывает порядок сложности вашего алгоритма.

Основные вещи:

• Эта сложность измеряется относительно размера записи
• Вы выбираете единичную операцию (обычно влияние или сравнение)
• Вы подсчитываете, сколько раз эта операция называется
• Постоянный член или постоянный коэффициент обычно игнорируется при использовании сложности, поэтому есличисло операций - 3 * n ^ 3 + 12, оно упрощено до n ^ 3 и также помечено O (n ^ 3)

a.) Будет запущен только один раз, нетцикл, сложность здесь тривиальна O(1)

b.) Вызовите n раз в цикле: O(n)

c.) Здесьмы решили проанализировать n (потому что это обычно возрастающая переменная в алгоритме).Количество вызовов n - 6, поэтому это O(n).

d.) Предположим, что 10 (n) - это размер вашего массива, а девять (i) - эторазмер минус один.Для каждого значения n мы должны перейти от 0 к n, затем от n-1 до 0. n * (n-1) операций, технически: O(n * 2), которые некоторые люди приблизительно обозначают как O(n).И то, и другое называется линейным временем, но отличается от наклона линии, о котором BigO не заботится.

e.) Цикл переходит от 0 к пау (2, n), что составляет от 1 до 2 ^ n, суммируется как O(2^n)

Answer 2

Если вы не учитываете cout как часть вашего измерения Big-O.

а) O (1) вы можете выполнять целочисленное присваивание за постоянное время.
б) O (n), потому что для цикла требуется n операций.
с) O (n - c) = O (n) константы исчезают в Big-O.
д.1) O (2 * n) = O (n) два линейных алгоритма времени заканчиваются линейным временем.
д.2) Если n растет при pow (2, n) = 2 ^ n, то число операций равно O (2 ^ n); однако, если n постоянно, оно будет расти с O (k), где k = 2 ^ 6 = 64, что будет линейным.

Answer 3

Эти примеры довольно просты. Сначала вам нужно определить основную ( simple ) операцию в коде и попытаться выразить число вызовов этой операции как функцию ввода.

Чтобы быть менее абстрактным:

а.)

Этот код всегда выполняется в постоянное время. Это время зависит от компьютера, задержки ввода-вывода и т. Д., Но практически не зависит от значения n.

б.)

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

с.)

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

* * 1 022 д.)

Этот код интересен. Операция внутри первого цикла является более сложной, но опять же она занимает более или менее постоянное количество времени. Так сколько раз он выполняется по отношению к n? Еще раз сравните с б.)

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

5.)

Последний кусок кода на самом деле довольно прост. Число простых операций внутри цикла равно n^2. Добавьте 1 к n, и вы получите вдвое больше операций.

Answer 4

a

n=6;
cout<<n<<endl;

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

b

n=16;
for (i=0; i<n; i++)
    cout<<i<<endl;

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

c

i=6;
n=23;
while (i<n) {
    cout<<i-6<<endl;
    i++;
}

Линейное время, O (n), такое же, какПример 2 выше.

d

int a[ ] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
n=10;
for (i=0; i<n; i++)
    a[i]=a[i]*2;
for (i=9; i>=0; i--)
    cout<<a[i]<<endl;

Линейное время, O (n).При увеличении n от 1 до бесконечности количество времени, необходимое для выполнения этих операторов, увеличивается линейно.Линейная линия в два раза круче, чем в примере 3, однако Big O Notation не заботится о том, насколько крута линия, она касается только того, как растут требования ко времени.Два цикла требуют линейно растущего количества времени при увеличении n.

e

sum=0;
n=6;
k=pow(2,n);
for (i=0;i<k;i++)
    sum=sum+k;

Создайте график того, сколько раз sum=sum+k выполняется, учитывая значениеn:

n     number_of_times_in_loop
1     2^1 = 2
2     2^2 = 4
3     2^3 = 8
4     2^4 = 16
5     2^5 = 32
6     2^6 = 64

По мере того, как n переходит от 1 к бесконечности, обратите внимание, как количество раз, когда мы находимся в цикле, экспоненциально увеличивается.2->4->8->16->32->64.Что произойдет, если я подключу n из 150?Число раз, которое мы будем в цикле, становится астрономическим.

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

Почему мы заботимся?

Как компьютерные ученые, мы заинтересованы в правильном понимании обозначения BigO, потому что мы хотим быть в состоянии сказать что-то подобное с уверенностью и убедительностью:

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

И еще лучше, если им не нравится то, что они слышат, вы можете доказатьэто с математикой.

Answer 5

Чтобы понять полное математическое определение, я рекомендую Википедию. Для простых целей big-oh является верхней границей алгоритма, учитывая подпрограмму, сколько раз он повторяется перед завершением, учитывая длину n. мы называем эту верхнюю границу O (n) или большой ой из n.

В коде доступ к элементу простого массива в c ++ - O (1). Это одна операция независимо от размера массива.

Линейная итерация по массиву в цикле for равна O (n)

Вложено для циклов O (n ^ 2) или O (n ^ k), если в цикле более одного вложенного элемента

Рекурсия с делением и захватом (кучами, бинарными деревьями и т. Д.) Равна O (lg n) или O (n lg n) в зависимости от операции.