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; 

}