Почему пузырьковый вид O (n ^ 2)?

int currentMinIndex = 0;

for (int front = 0; front < intArray.length; front++)
{
    currentMinIndex = front;

    for (int i = front; i < intArray.length; i++)
    {
        if (intArray[i] < intArray[currentMinIndex])
        {
            currentMinIndex = i;
        }
    }

    int tmp = intArray[front];
    intArray[front] = intArray[currentMinIndex];
    intArray[currentMinIndex] = tmp;
}

Внутренний цикл итерации: n + (n-1) + (n-2) + (n-3) +... + 1 раз.

Внешний цикл повторяется: n раз.

Итак, вы получаете n * (сумма чисел от 1 до n)

Разве что n * (n * (n + 1)/2) = n * ((n ^ 2) + n/2)

Что было бы (n ^ 3) + (n ^ 2)/2 = O (n ^ 3)?

Я уверен, что делаю это неправильно. Почему не O (n ^ 3)?

Ответ 1

Вы правы, что внешний цикл повторяется n раз, а внутренний цикл повторяется и в n раз, но вы выполняете двойной учет работы. Если подсчитать всю работу, проделанную суммированием работы, выполняемой на каждой итерации цикла верхнего уровня, вы получите, что первая итерация работает n, вторая n - 1, третья n - 2 и т.д., Так как i-я итерация петли верхнего уровня имеет внутренний цикл, выполняющий работу n - i.

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

Вы делаете ошибку, пытаясь объединить эти две стратегии. Верно, что внешний цикл n работает в первый раз, затем n - 1, затем n - 2 и т.д. Однако вы не умножаете эту работу на n, чтобы получить общее количество. Это будет считать каждую итерацию n раз. Вместо этого вы можете просто суммировать их.

Надеюсь, это поможет!

Ответ 2

Внутренний цикл повторяется IN TOTAL, как вы сказали n + (n-1) + (n-2) + (n-3) +... + 1 раз. Таким образом, это O (n + (n-1) + (n-2) + (n-3) +... + 1) = O (n (n + 1)/2) = O (n ^ 2)

Ответ 3

Внутренняя петля повторяется n раз (в худшем случае):

for(int i = front; i < intArray.length; i++)

Внешний цикл повторяется n раз:

for(int front = 0; front < intArray.length; front++)

Поэтому O (n ^ 2)

Ответ 4

Как вы в основном вычисляете N...

Каждая строка: +1
Каждый цикл * N

Итак, вы начинаете добавлять числа в свой первый цикл, теперь у вас есть N + 1, вы продолжаете идти, и в итоге вы получаете N * N или N ^ 2 за время плюс некоторое число. Вытягивание числа, как правило, незначительное по сравнению с N.

Довольно много N представляет собой представление всех элементов в виде петли типа 1,2,3... N. Таким образом, он просто представляет число, а не сколько раз цикл, циклы.

Ответ 5

k=1(sigma k)n = n(n+1)/2
because:
  s = 1 +  2    + ... + (n-1) + n
  s = n + (n-1) + ... + 2     + 1
+)
===================================
  2s = n*(n+1)
   s = n(n+1)/2
in bubble sort, 
(n-1) + (n-2) + ... + 1 + 0 times compares 
which means, k=0(sigma k)n-1
, k=0(sigma k)n-1 equals [k=1(sigma k)n] - n
therefore, n(n+1)/2 - n = n(n-1)/2
which is 1/2(n^2-n) => O(1/2(n^2-n))
in big O notation, we remove constant, so
O(n^2-n)
n^2 is larger than n
O(n^2)

Ответ 6

Просто для того, чтобы иметь некоторую версию пузырьковой версии Python...

def bubble_sort(input):
    n = len(input)
    iterations = 0
    for i in xrange(n, 1, -1):
        for j in range(0, i - 1):
            iterations += 1
            if input[j] > input[j+1]:
                input[j],input[j+1] = input[j+1],input[j]

    print iterations
    return input

Итерации были добавлены во внутренний цикл для подсчета полных итераций. Ничего общего с пузырьковой сортировкой.

Передача массива из 5 элементов приводит к 15 итерациям не 25. Также, когда предварительно отсортировано, это также приводит к 15 итерациям. Но сложность также должна учитывать сравнение и обмен.