Вложено для цикла в Big Oh Complexity

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

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

Источник

4 ответа

Решение

Как вы упомянули

Каждый занимает единицу 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)

Всего n терминов

2 * total_time = (n+1) * n

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

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

Меньшие члены и постоянные коэффициенты игнорируются для большой сложности O.

В следствии

O (N ^2)

Источник 
      for(int i = 0; i < n; i++){  // outer loop
    for(int j = 0; j < i; j++){  // inner loop
        //do swap stuff, constant time
    }
}

В первой итерации внешнего цикла (i = 0) внутренний цикл не выполняется.

Во второй итерации внешнего цикла (i = 1) выполняется внутренний цикл once.

На третьей итерации внешнего цикла (i = 2) выполняется внутренний цикл twice.

Итак, на последней итерации внешнего цикла (i = n) выполняется внутренний цикл n times.

Таким образом, общее количество выполнений этого кода равно

1 + 2 + 3 + … + n

= n(n + 1) / 2(Формула суммы натуральных чисел)

= ((n^2) + n) / 2

= O(n^2)

——————

Также взгляните на эти

  1. /questions/39713898/kakova-slozhnost-vremeni-naihudshego-sluchaya-dlya-etogo-algoritma/62321477#62321477
  2. /questions/10543993/chto-takoe-big-o-vlozhennogo-tsikla-gde-chislo-iteratsij-vo-vnutrennem-tsikle-opredelyaetsya-tekuschej-iteratsiej-vneshnego-tsikla/62055626#62055626
  3. /questions/39522799/vremennaya-slozhnost-vlozhennogo-tsikla-for/61824023#61824023
  4. /questions/21671824/ispolzuya-big-o-notation-kakova-pravilnaya-metka-dlya-etogo-algoritma/62348199#62348199
  5. /questions/59462490/on-i-funktsiya-vremennoj-slozhnosti-dannogo-koda/59574440#59574440
Источник

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

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

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

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

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

Источник

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

п (п +1)/2

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

Источник
Другие вопросы по тегам