Złożoność obliczeniowa

[Perezek]

1.a)Podaj definicję pesymistycznej i optymistycznej złożoności obliczeniowej.
b)Oblicz złożoność obliczeniową w ogólnym przypadku, pesymistyczną i optymistyczną dla podanego poniżej algorytmu.
c)Wykonaj poniższy algorytm dla zbioru liczb: 7, 1, 5, 2, 2, 6, 1.

Algorytm_A(tablica_T, rozmiar tablicy N){
for(j=2,j<=N,j++){
x=T[j];
i=j-1;
while(i>0 && T<=x){
T[i+1]=T;
i=i-1;
}
T[i+1]=x;
}
}

[argv]

Pesymistyczna - to największy możliwy czas działania dla danych rozmiaru n a formalnie to supremum kosztu algorytmu po wszystkich danych rozmiaru n (bierzemy supremum a nie nie maksimum bo teoretycznie dane mogą być nieskończone)
Optymistyczna - infimum kosztu algorytmu bla bla ... czyli najkrótszy możliwy czas działania

Operacja dominująca to porównanie w while
Pesymistycznie dla insertion-sort porownanie w while wykona się i razy
czyli \(\displaystyle{ \sum_{i=2}^{n}i = \frac{1}{2}n^{2} + O(n)}\)

Ogólny przypadek więc to \(\displaystyle{ O(n^{2})}\)

A optymistycznie to zauważamy że insertionsort dla n-elementowej tablicy wykonuje liczbę porównań
równą liczbie inwersji + (n-1). Ciąg posortowany (czy prawie posortowany) ma liniowa liczbe inwersji stąd
koszt optymistyczny to \(\displaystyle{ \theta(n)}\) czyli liniowy.

Zasymuluj sobie sam