Оценка сложности рекурсивного алгоритма

[Dext]

Подскажите, за которое время работает рекурсивная функции F

Используется синтаксис Javascript

function F(k,A)  // A - массив. Индексация с 0.
{ 
    var n = A.length;             //Количество элементов в массиве A.

    if (k == n-2) return G( A[n-2], A[n-1] );   // Функция G - работает за O(n).
                                                //  где n - кол.-во элементов массива A.
    else return G( A[k], F(k+1,A) );                 
}
                                                          
// За сколько работает функция F ?
//

[Xaositect]

А как функция G может работать за $O(n)$, если она не получает на вход массив?

[Dext]

Xaositect в сообщении #741716 писал(а):

А как функция G может работать за $O(n)$, если она не получает на вход массив?

Функция G получает даже два массива. Просто A - это двумерный массив (массив массивов).
Не стал уточнять - думал, что это не существенно.

Используется синтаксис Javascript

function F(k,A)  // A - двумерный массив (массив массивов). Индексация с 0.
{ 
    var n = A.length;             //Количество элементов в массиве A.

    if (k == n-2) return G( A[n-2], A[n-1] );   // Функция G - работает за O(k+m).
                                                //  где k и m - количества элементов в массивах A[n-2] и A[n-1].
    else return G( A[k], F(k+1,A) );                 
}
                                                          
// За сколько работает функция F ?
//
 

[Xaositect]

Понятно. Просто количество элементов в массиве A и количества элементов в массивах A[i] это разные вещи.
Теперь ответ зависит от размера массива, возвращаемого функцией G.

Кстати, если я правильно угадал язык Javascript, эта функция пишется как A.reduceRight(G), правда для старых IE надо добавить shim отсюда.

[Dext]

Xaositect в сообщении #741727 писал(а):

Понятно. Просто количество элементов в массиве A и количества элементов в массивах A[i] это разные вещи.
Теперь ответ зависит от размера массива, возвращаемого функцией G.

Функция всегда возвращает массив длины k+m.

Xaositect в сообщении #741727 писал(а):

Кстати, если я правильно угадал язык Javascript, эта функция пишется как A.reduceRight(G), правда для старых IE надо добавить shim.

Верно - Javascript, но эти методы не нужны.

Помогите оценить сложность функции F.

[Xaositect]

Dext в сообщении #741729 писал(а):

Помогите оценить сложность функции F.

Ну, давайте напишем рекуррентное соотношение и будем считать. Пусть длина массива A равна $n$, а длины массивов A[i] равны $m_i$. Пусть сложность ф-и G(A,B) от двух массивов длины $a$ и $b$ будет $g(a,b)$, а сложность ф-и F(k, A) будет $f(k)$, а длина возвращаемого ей массива - $l(k)$
Тогда $f(n - 2) = g(m_{n-2}, m_{n-1})$, $l(n-2) = m_{n-2} + m_{n-1}$, $f(k) = f(k + 1) + g(m_k, l(k+1))$, $l(k) = m_k + l(k + 1)$. Отсюда сразу видно, что $l(k) = \sum_{i = k}^{n-1} m_i$ и

$$f(k) = g(m_k, \sum_{k+1}^{n-1} m_i) + g(m_{k+1},\sum_{k+2}^{n-1} m_i) + g(m_{k+2},\sum_{k+3}^{n-1} m_i) + \dots +g(m_{n-2}, m_{n-1})$$

. Если $g(a, b) = O(a + b)$, то

\begin{multline*}f(k) = O(\sum_{k}^{n-1} m_i) + O(\sum_{k+1}^{n-1} m_i) + O(\sum_{k+2}^{n-1} m_i) + \dots + O(m_{n - 2} + m_{n - 1}) =\\ O(m_k + 2m_{k + 1} + 3m_{k + 2} + \dots + (n - k - 1)m_{n - 2} + (n - k - 1)m_{n - 1})\end{multline*}

Если все $m_i$ примерно одинаковы, то это будет $O(m(n-k)^2)$

[Dext]

Xaositect спасибо!

Помогите ещё разобрать на примере. Без решения - просто оценка сложности, надеюсь сам воспроизведу решение. Набросал некоторое подобие сортировки слиянием с использованием данной рекурсии.

function merge(A,B)      // Функция слияния двух массивов.
{                        // A и B - упорядоченные массивы.

    var N = A.length, M = B.length, C = [];

    for (var i=0, j=0, k=0; k<N+M; k++)
     { if (i==N){ C[k] = B[j++]; continue; }
       if (j==M){ C[k] = A[i++]; continue; }
       C[k] = (A[i]<B[j]) ? A[i++] : B[j++];
     }
                        // На выходе упорядоченный массив,
    return C;           //  состоящий из элементов A и B.
}
// Почти очевидно, что функция работает за O(N+M).

function MergeSort(k,A)   // Некоторое подобие сортировки слиянием ))
{                         //  Чисто для образовательных целей.
    var n = A.length;

    if (n<2) return A;

    if (k == n-2) return merge( [A[n-2]], [A[n-1]] );
    else return merge( [A[k]], MergeSort(k+1,A) );
}
// За сколько работает функция MergeSort ?

[Xaositect]

Dext в сообщении #741741 писал(а):

 if (k == n-2) return merge( [A[n-2]], [A[n-1]] );
else return merge( [A[k]], MergeSort(k+1,A) );

А внешние квадратные скобки у A[i] тут точно должны быть? Функция делает что-то малоосмысленное.

[Dext]

Xaositect в сообщении #741745 писал(а):

А внешние квадратные скобки у A[i] тут точно должны быть?

Прошу прощения - опять не всё записал.

Параметр A в функции MergeSort одномерный массив. А внешние квадратные скобки у A[i] в merge( [A[n-2]], [A[n-1]] ) точно должны быть, т.к. аргументами функции merge(A,B) являются массивы.
То есть для корректного вызова merge() в MergeSort() мы пишем элементы (числа) A[i] массива A в merge() как одноэлементные массивы [A[i]].

[Xaositect]

А, то есть у вас сортировка вставками на самом деле.
Ну в общем пишите, какой длины у Вас будут аргументы функции merge в каждом рекурсивном вызове.

[Dext]

Ещё забыл написать, что при вызове MergeSort(k,A) для полной сортировки массива A параметр k всегда полагаем равным 0.

-- Вс июн 30, 2013 01:04:07 --

Xaositect в сообщении #741753 писал(а):

Ну в общем пишите, какой длины у Вас будут аргументы функции merge в каждом рекурсивном вызове.

Такие длины?

Вызовы MergeSort | Длины аргументов merge
       1-й              N = 1, M = 1
       2-й              N = 1, M = 2
       3-й              N = 1, M = 3
       ...                  ...
       n-й              N = 1, M = n

[Xaositect]

Угу.
Соотвественно, сложность будет примерно сумма сложностей функции merge при этих длинах аргументов. Порядка $n^2$ в итоге получается.

[Dext]

Спасибо, разобрался.