Почему инверсия «разделяй и властвуй» считается n * log (n)? - PullRequest
0 голосов
/ 09 мая 2020

Многие ресурсы, которые я просмотрел, говорят, что метод подсчета инверсии разделяй и властвуй имеет время выполнения nlog (n), но я не понимаю почему. Я знаю, что сортировка слиянием имеет время nlog (n), потому что количество разделяющих массивов до тех пор, пока базовый случай не станет log (n), а время выполнения слияния будет (n) каждый раз, когда нам нужно объединить два массива.

Но когда мы «копируем» поверх сортировки слиянием, нам нужно сравнить две половины массива:

[a,b,c] and [d,e,f] 

«a» нужно сравнить с «d» и «e» и «f» наихудший сценарий и так далее и так далее для всех элементов в левом массиве. Таким образом, кажется, что только это будет иметь время выполнения n ^ 2/4, поэтому время выполнения инверсии «разделяй и властвуй» al go не будет n ^ 2log (n)?

1 Ответ

1 голос
/ 09 мая 2020

[a, b, c] и [d, e, f]

«a» необходимо сравнить с «d» и «e» и «f» наихудшим сценарием.

l oop

while (not at end of A && not at end of B)

всегда имеет O (| A | + | B |) шагов, независимо от результатов сравнения. Для слияния и подсчета не существует ни лучшего, ни худшего случая.

Сортировка и подсчет (L)

if list L has one element
    return (0, L)

Divide the list into two halves A and B
(rA, A) ← Sort-and-Count(A)
(rB, B) ← Sort-and-Count(B)
(rC, L) ← Merge-and-Count(A, B)
r = rA + rB + rC
return (r, L)

Слияние -и-Счетчик (A, B)

    curA = 0; curB = 0;
    count = 0;
    mergedList = empty list

    while (not at end of A && not at end of B)
        a = A[curA]; b = B[curB];
        if (a < b)                             // only one comparison
            append a to mergedList;
            curA++;
        else
            append b to mergedList;
            curB++;
            count = count + num elements left in A

    if (at end of A) 
        append rest of B to mergedList;
    else
        append rest of A to mergedList;

    return (count, mergedList);
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...