Не удается решить временную сложность этого алгоритма экспоненциальной сортировки

A[n];
Sort(p,r) 
{
    if (A[p] > A[r]) then
        A[p]<->A[r];    //exchange
    if (p+1 >= r) then
        return;
    q <- (r-p+1) / 3;
    Sort(p, r-q);    // 2/3 of head
    Sort(p+q, r);    // 2/3 of tail
    Sort(p, r-q);    // again, 2/3 of head
 }

Привет всем. Это проблема, в которой я изучаю. Алгоритм отлично работает для сортировки. n time 15 0.004 16 0.008 17 0.017 18 0.034 19 0.072 20 0.143 21 0.283 22 0.572 23 1.154 24 2.296 25 4.604 26 9.23 27 18.517 выше, как он принимает время для n. (пример: если n равно 15, работайте так. Sort(0,14))

Сложность времени кажется экспоненциальной 2 ^ n. Правильно?

Но я не знаю, как это, потому что я думал, что T(n) = 3T((2/3)*n) + 1 = 3^n. Это не соответствует тому, что у меня есть в реальном времени... Нужна помощь, пожалуйста.


sorting algorithm time-complexity exponential
person user3524577    schedule 11.04.2014    source источник
comment
Вы уверены, что ваша граница повторения жесткая?   -  person David Eisenstat    schedule 11.04.2014

Ответы (2)


arrow_upward
0
arrow_downward

Не знаю, что сказать...
Я посмотрел код, который вы разместили, и думаю, что T(n) = 3⋅T((2⋅n/3) + 1 правильный. НО тогда основная теорема говорит T(n) = O(nlog3/2(3)) ≈ O(n2.7095) или что-то в этом роде. Я просто не вижу экспоненциального времени. Поэтому я пишу тест на PHP.

function WiredSort($p, $r, &$A)
{
    if($A[$p] > $A[$r])
    {
        $temp = $A[$p];
        $A[$p] = $A[$r];
        $A[$r] = $temp;
    }

    if($p + 1 >= $r)
        return;

    $q = round(($r-$p+1)/3);
    WiredSort($p, $r-$q, $A);
    WiredSort($p+$q, $r, $A);
    WiredSort($p, $r-$q, $A);
}

Вызов WiredSort(0,n-1,$A) выполняется
для n=100 через 0,056003 с,
для n=110 через 0,056003 с,
для n=1000 через 0,390766 с.

Это также не выглядит экспоненциальным для меня.

Откуда вы взяли свои данные?

person AbcAeffchen    schedule 11.04.2014

arrow_upward
0
arrow_downward

Из временной сложности с использованием теоремы мастеров в уравнении T(n) = 3*T(2/3*n) + 1 мы получаем T(n) = O(n^(log(3/2)(3)) = O(n^(2.7)), а не O(3^n), поэтому в вашей реализации проблемы есть что-то ужасно неправильное, иначе вы не сможете получить экспоненциальный рост для этого алгоритма.

person Vikram Bhat    schedule 12.04.2014