Algorytmy i struktury danych

Złożoność algorytmów

1. Z

ŁOŻONOŚĆ ALGORYTMÓW

Jest to jeden z najważniejszych parametrów charakteryzujących algorytm. Decyduje on o efektywności całego
programu. Podstawowymi zasobami systemowymi uwzględnianymi w analizie algorytmów są czas działania
oraz obszar zajmowanej pamięci. Na złożoność czasową składają się dwie wartości: pesymistyczna, czyli taka,
która charakteryzuje najgorszy przypadek działania oraz oczekiwana. Najczęściej algorytmy mają złożoność
czasową proporcjonalną do funkcji:
a) log(n)- złożoność logarytmiczna
b) n - złożoność liniowa
c) nlog(n) - złożoność liniowo-logarytmiczna
d) n

2

- złożoność kwadratowa

e) n

k

- złożoność wielomianowa

f) 2

n

- złożoność wykładnicza

g) n! - złożoność wykładnicza, ponieważ n!>2

n

już od n=4

2. Z

ADANIA

Zadanie1.
Podaj złożoności w notacji O() dla algorytmów, w których liczba operacji wyrażona jest wzorami:
a) log100 + n + n
b) 2n(n + 2)+4n(2n - 1)(n - 2)
c) 2n + 3 + log n
d) n – n + 3logn
e) n(n*n + logn - 19)
f) log(2 + n - n(13 - 3*4))

Zadanie2.
Uporządkuj w kierunku rosnącym następujące złożoności obliczeniowe algorytmów:
O(n),O(log n),O(n!),O(2n) .

Zadanie2.
Dana jest tablica n-elementowa tab. Oszacuj złożoność czasową algorytmu sortowania bąbelkowego tej tablicy:
for (int i=1; i<n; i++)
{

for (int j=n-1; j>=i; j--)
{

if (tab[j-1]>tab[j])
{

t=tab[j-1]
tab[j-1]=tab[j];
tab[j]=t;

}

}

}

Zadanie3.
Dana jest tablica n-elementowa tab. Oszacuj złożoność czasową algorytmu sortowania przez selekcję tej
tablicy:
for (int i=1; i<n; i++)
{

min=i;
for (int j=i+1; j<n; j++)
{

if (tab[j]<tab[min]) min=j;

}
t=tab[min]
tab[min]=tab[i];
tab[i]=t;

}