obliczanie złożności algorytmu + obliczanie równania rekuren

[Kuna]

Mam takie zadanie:

Ułóż równanie rekurencyjne do algorytmu podanego poniżej i rozwiąż je.

Kod: Zaznacz cały

#include <iostream.h>

const n=12;

int tan[n]={40,29,2,1,6,18,20,32,34,39,23,41};

void zamiana(int &a, int &b) {
        int temp=a;
        a=b;
        b=temp;
}

void qsort(int *tab, int left, int right) {
        if (left<right) {
                int m=left;
                for (int i=left+1; i<right; i++)
                        if (tab[i]<tab[left])
                                zamiana(tab[++m], tab[m]);
                zamiana(tab[left], tab[m]);
                qsort(tab,left,m-1);	// zastosuj qsort na lewo od m
                qsort(tab,m+1,right);	// zastosuj qsort na prawo od m
        }
}

void main() {
        for (int i=0;i<n;i++)
                cout<<tab[i]<<" ";
        cout<<endl;
        qsort(tab, 0, n-1);
        for (i-0;i<n;i++)
                cout<<tab[i]<<" ";
        cout<<endl;
}

Czy ktoś mógłby powiedzieć jak to się robi? Na co zwracać uwagę przy algorytmach rekurencyjnych?

[Dumel]

do QuickSorta raczej ciężko ułożyć równanie rekurencyjne, a złożoność tego algorytmu można ograniczyć jedynie od góry przez \(\displaystyle{ O(n^2)}\)
ogólnie przy obliczaniu złożoności algorytmów rekurencyjnych korzystamy z tw. o rekurencji uniwersalnej: ... iwersalnej.

QuickSorta można przysieszyć w przypadku pesymistycznym poprzez wyznaczanie mediany zbioru i użycie jej jako elementu rozdzielającego- wtedy bedzie działał w czasie \(\displaystyle{ O(nlogn)}\)

[kadiii]

Polecam podstawową księgę do tego typu rzeczy, Wprowadzenie do algorytmów Cormena ... - jest tam to w prosty sposób wyłożone, są i równania rekurencyjne i opis dlaczego tak a nie inaczej. Nie będę więc tu sie rozpisywał, zapraszam do lektury.