Вложенный цикл в Большой Oh Сложность

for(int i = 0; i < n; i++) { 
    for(int j = 0; j < i; j++){ 
     //do swap stuff, constant time 
    } 
}

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

источник

2015-02-11 Anonymous

У вас есть N элементов, каждый с 1 операцию и для каждой операции вы делаете N больше операций. – Hristo

Внутренний цикл будет работать: '1 + 2 + 3 + 4 + ... + n = n (1 + n)/2 => O (n^2)' – alfasin

@alfasin Не могли бы вы быть более конкретными с вашей ответ ? –

Как упоминалось

Каждый блок занимает 1 - O (1)

Таким образом, каждая итерация внутреннего цикла принимает 1, 2, 3, ..., N единицу времени ,

total_time = 1 + 2 + 3 + ... + (n-2) + (n-1) + n

реверса

total_time = n + (n-1) + (n-2) + ... + 3 + 2 + 1

Добавление

2 * total_time = (n+1) + (n+1) + (n+1) + ... + (n+1) + (n+1) + (n+1)

Есть всего п членов

2 * total_time = (n+1) * n 

=> total_time = (n+1) * n/2 

=> total_time = n^2/2 + n/2

Lower условия и постоянные коэффициенты безнадзорных для большой сложности O.

В результате

O (N^2)

источник

2015-02-11 08:04:19

Функция, петли от I = 1 до п, а затем имеет внутренний контур, который идет от 1 до я пошел бы, хотя число итераций, равное этой формуле:

п (п + 1)/2

Как вы можете видеть, когда мы избавимся от всего, кроме основного показателя, то заканчивается O (N^2)

источник

2015-02-11 07:53:19 SabaRish

прочитайте также http: // stackoverflow.com/questions/362059/what-is-the-big-o-of-a-nested-loop-where-number-of-iterations-in-the-inner-loop – SabaRish

это также: http://stackoverflow.com/questions/21372927/big-o-and-nested-loops – SabaRish

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

В вашем случае внутренний цикл выполняется i раз. Значения для i равны 0, 1, 2, ..., n-1. Поэтому вам нужна формула, которая вычисляет эту сумму, и это ваш результат.

Вы считаете, что один цикл равен O (n). Это чепуха. Это зависит от цикла.

for (i = 1; i < n; i *= n)

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

источник

2015-02-11 07:56:28 gnasher729

'for (i = 1; i

Я думаю, что он/она имел в виду 'i * = 2'. –

Вложенный цикл в Большой Oh Сложность

ответ

Смежные вопросы