Найти рекуррентное соотношение для этой рекурсивной функции?

Question

Рассмотрим следующую функцию:

g(A, i, j) {
    print("g", i, j);
    n := j-i+1;
    if (n == 2) {
        if (A[i] > A[j]) swap A[i] and A[j];
    }
    else {
        for(k := 0 to n/4-1) swap A[i+n/4+k] with A[i+n/2+k];

        // swap 2nd and 3rd quarters
        g(A, i, i+n/2-1); // recurse on 1st and 2nd quarters
        g(A, i+n/2, j); // recurse on 3rd and 4th quarters
        g(A, i+n/4, i+3n/4-1); // recurse on 2nd and 3rd quarters
    }
}

Как бы я вывел рекуррентное отношение для времени выполнения функции g? Я видел, что ответом является

T (n) = 3T (n / 2) + O (n).

В этом выражении T ( о) значит "время?" Откуда берется n / 2? И, в более общем смысле, как мне найти подобные повторения?

Answer 1

Вы можете прочитать повторение

T (n) = 3T (n / 2) + O (n)

как определение некоторой функции T (n) это определяет, сколько времени требуется для запуска функции g в массиве, который содержит всего n элементов. Поскольку функция g является рекурсивной, определение T (n) также рекурсивно.

Здесь 3T (n / 2) означает, что «сделано три рекурсивных вызова, каждый из которых должен подзадача размером n / 2 ". Чтобы понять, почему это так, обратите внимание, что в рекурсивном случае g делает три вызова для себя в диапазонах

g(A, i, i+n/2-1); // recurse on 1st and 2nd quarters
g(A, i+n/2, j); // recurse on 3rd and 4th quarters
g(A, i+n/4, i+3n/4-1); // recurse on 2nd and 3rd quarters

Общее количество элементов в каждом диапазоне равно n / 2 (вы понимаете, почему ?), следовательно, 3T (n / 2) бит.

«+ O (n)» входит, потому что алгоритм в рекурсивном случае выполняет линейный объем работы независимо от работы, выполненной для делать рекурсивные звонки. Это следует из for l oop над рекурсивными вызовами.

Получив рекурсию, подобную этой, вы можете использовать основную теорему для преобразования рекурсивного определения T (n) в прямую оценку того, как ведет себя T (n). Здесь время выполнения составляет

T (n) = O (n ^{log ₂ 3} ),

который мы получаем, рассматривая случаи основной теоремы, чтобы понять, какая из них применима.