Анализ больших О с рекурсивным деревом сортировки Штоге

Question

Я пытаюсь найти Big O для сортировки марионеток. Из Википедии

algorithm stoogesort(array L, i = 0, j = length(L)-1)
     if L[j] < L[i] then
         L[i] ↔ L[j]
     if j - i > 1 then
         t = (j - i + 1)/3
         stoogesort(L, i  , j-t)
         stoogesort(L, i+t, j  )
         stoogesort(L, i  , j-t)
     return L

Я плохо разбираюсь в производительности ... Я нарисовал дерево рекурсии

Я верю ...:

• высота: log(n)
• работа на уровне 0: n // начинать с уровня 0 или 1?
• работа на уровне 1: 2n
• работа на уровне 2: 4n
• работа на уровне 3: 8n
• работа на уровне журнала (n): (2^log(n))n = O(n^2)? 2^log2(n) = n, а что на самом деле дает 2^log3(n)?

Так что это O(n^2 * log(n)) = O(n^2)? Это далеко от O(n^(log3/log1.5)) ...

Википедии

Answer 1

Размер проблемы на уровне k равен (2/3) ^k n.Размер на нижнем уровне равен 1, поэтому при настройке (2/3) ^k n = 1 глубина k = log _1.5 n (разделить обе стороны на (2/3)) ^k , взять базу журналов 1.5).

Количество вызовов на уровне k составляет 3 ^k .На уровне k = log _1,5 n это 3 ^{log _1,5 n} = ((1,5) ^{log _1,5 3} ) ^{log _1.5 n} = ((1.5) ^{log _1.5 n} ) ^{log _1.5 3} = n ^{log _1.5 3} = n ^{log 3 / log 1.5} .

Поскольку работа на каждом уровне увеличивается геометрически,работа на листьях доминирует.

Answer 2

Вы можете использовать Основную теорему , чтобы найти этот ответ. Из алгоритма видно, что рекуррентное соотношение:

T (n) = 3 * T (2/3 n) + 1

Применение теоремы:

f (n) = 1 = O (n ^c ), где c = 0. a = 3, b = 3/2 => log3 / 2 (3) = ~ 2,70

Поскольку c

T (n) = O (n ^{log3 / 2 (3)} ) = O (n ^2.70 )

Answer 3

Возможно, это может помочь:

/**********************************************************************
 * Complexity:
 * This algorithm makes exactly one comparison on each step.
 * On each step - algorithm divide initial array of size n :
 * on 3 arrays with (2*n / 3) sizes
 *                                           N
 *                                       /   |   \
 *                                   2N/3  2N/3  2N/3
 *                                   /
 *                              (2N/3)2/3
 *                                 /
 *                               ...
 *                               /
 *                           N * (2/3)^k = 1
 * By considering this tree we can find the depth - k:
 * N * (2/3)^k = 1                  =>>
 * N = 1 / (2/3)^k                  =>>
 * N = (3/2)^k                      =>>
 * log(3/2, N) = log(3/2, (3/2)^k)  =>>
 * k = log(3/2, N) (!!!)
 *
 * On each step algorithm makes 3^k comparisons =>> on the last step we will get:
 *                                     3^(log(3/2, N)) =>> N^(log(3/2, 3))
 * comparisons.
 *
 * We can compute the full work:
 * 1 + 3 + 9 + ... + 3^(log(3/2, N))
 * by using geometric progression formulas.
 * 
 *************************************************************************/
public static void sort(Comparable[] a, int lo, int hi) {
    if (lo >= hi) return;
    if (less(a[hi], a[lo])) exch(a, hi, lo);
    if (hi - lo + 1 > 2) {
        int t = (hi - lo + 1) / 3;
        sort(a, lo, hi - t);
        sort(a, lo + t, hi);
        sort(a, lo, hi - t);
    }
}

Answer 4

t (n) = 3⋅t (2 * n / 3) + Θ (n)

h = 1 + log _3/2 (n)

Попробуйте посчитать. это легко.

На каждом уровне мы имеем сложность 3 ⁱ ⋅c, где c - некоторая постоянная, а i - высота этого конкретного уровня

t (n) = Σ _{i = 0, ..., ч} c⋅3 ⁱ

t (n) = n-2 ^{log₃ (n)} / 2 ^{log₃ (n) + 1}

тогда это простая геометрическая прогрессия.

Answer 5

Если мы определим T (n) как ответ (j-i + 1 = n), мы получим:
T (n) = 3 * T (n / 1,5) + O (1)

Вы можете решить это, используя Основную теорему , и ответ будет тета (n ^ log (3,1.5)) = тета (n ^ (журнал 3 / журнал 1.5))

Вы можете доказать это, используя индукцию по n тоже.

Также допустимо использование дерева рекурсии:
k = количество уровней = log (n, 1,5)
ans = 1 + 3 + 3 ^ 2 + ... + 3 ^ k = тета (3 ^ k) = тета (3 ^ log (n, 1.5)) = тета (n ^ log (3,1.5))