Рекурсия для времени выполнения рекурсивной сортировки вставкой - PullRequest
Новая
       26

Рекурсия для времени выполнения рекурсивной сортировки вставкой

2 голосов
/ 07 сентября 2011

В настоящее время мне поручено написать рекурсивную версию алгоритма сортировки вставок.И я это сделал.На самом деле, вот что: 

void recursiveInsertionSort(int* inputArray, int p, int q)
{
  while (q > p)
  { 
     recursiveInsertionSort(inputArray, p, q-1);
     if (inputArray[q-1] > inputArray[q])
     {
         int temp = inputArray[q];
         int temp2 = inputArray[q-1];
         inputArray[q] = temp2;
         inputArray[q-1] = temp;
         q--;
     }
  }
}

Моя проблема двоякая.Во-первых, я не уверен, правильное ли отношение рекуррентности, с которым я пришел.Я придумал 

T(n) = T(n-1) + T(n^2)

в качестве рекуррентного отношения.Это правильно?Я прыгаю между этим и просто 

T(n) = T(n^2)

Во-вторых, я должен использовать алгебру, чтобы доказать, что 

f(n) = ((n+1)n / 2)

решает эту рекуррентную связь.Что мне действительно тяжело делать, потому что A. Я не уверен, что мой рецидив правильный, и B. Я иногда ужасно разбираюсь в математике.

Любая помощь по любому из вопросов будеточень признателен.

Спасибо.

Хорошо, мне удалось выяснить это с помощью профессора математики: P Я собираюсь оставить это здесь, чтобы другие знали, как это сделать.,Кто-то должен скопировать это как ответ: D

Таким образом, рекуррентное отношение для этого должно быть T (n) = T (n-1) + n, а не то, что у меня изначально было, это было главной проблемой.Зачем?Ну, это время, которое требуется для выполнения рекурсивного обратного хода, который равен n-1, поскольку, если бы вы перешли к n, у вас был бы только один элемент, и он уже отсортирован.Плюс время, необходимое для выполнения одной вставки или одной фактической сортировки.

Причина, по которой это n, заключается в том, что когда вы туда попадаете, вы проверяете одно число на каждое число перед тем, как оно окажется на n

Теперь, как вы показываете, что эта функция f (n) решает T (n)?

Хорошо, мы знаем, что f (n) решает T (n).Это означает, что вы можете сделать это: 

We know that f(n) is equal to (n(n+1))/2 . So if T(n) is equal to T(n-1) + n, that means we take away 1 from every n in f(n) and then plug that into T(n).

That gives us T((n+1-)n-1)/2)) + n . That simplifies to T((n(n-1)/2) + n. Take that + n thats out there and multiply it by 2/2 to be able to have it all over a common denominator. Giving you (n^2 - n + 2n)/2 . Simplifies down to ((n^2) + n)/2 which further simplifies to, if you factor out an n, (n(n+1))/2. Which is f(n).

Woo!

...