Klasyfikacja złożoności 

obliczeniowej

Złożoność czasowa

Definicja 1. 

Złożoność obliczeniowa (czasowa) 

algorytmu A jest to związek między rozmiarem danych, 
a czasem wykonywania algorytmu.

Miarą czasu algorytmu może być:

•

liczba instrukcji,

•

liczba operacji arytmetycznych,

•

liczba wywołań rekurencyjnych funkcji (oraz czasu 
ich działania),

•

liczba porównań.

•

log(n)- złożoność 
logarytmiczna 

•

n - złożoność liniowa 

•

nlog(n) - złożoność 
liniowo-logarytmiczna 

•

n

2

 - złożoność 

kwadratowa 

•

n

k

 - złożoność 

wielomianowa 

•

2

n

 - złożoność 

wykładnicza 

•

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

n

 już od n=4

Klasy złożoności algorytmów

•

Klasa P, to problem decyzyjny, dla którego rozwiązanie 
można znaleźć w czasie wielomianowym.

•

Klasa NP, to klasa, do której należą wszystkie problemy 
decyzyjne, które rozwiązuje niedeterministyczny 

algorytm wielomianowy, 

•

Klasa NP-zupełne, czyli problem zupełny w klasie NP ze 
względu na redukcje wielomianowe, to problem, który 

należy do klasy NP oraz dowolny problem należący do 
NP może być do niego zredukowany w czasie 

wielomianowym. 

•

Klasa NP-trudny - problem równie trudny, jak problemy 
NP-zupełne, jednak niekoniecznie należący do klasy NP 

Problem komiwojażera

Problem komiwojażera jest to zagadnienie z teorii 
grafów, polegające na znalezieniu minimalnego cyklu 
Hamiltona w pełnym grafie ważonym. 

Jest to przykład problemu NP-zupełnego.

Problem optymalizacyjnego 

szeregowania zadań 

Mamy daną skończoną liczbę prac, składających się z 
łańcucha operacji, skończoną liczbę maszyn, każda 
maszyna potrafi obsługiwać jedną operację w danym 
momencie. Wiedząc, że każda operacja ma być 
przetwarzana na danej maszynie nieprzerwanie, przez 
czas o określonej długości, znaleźć taki podział prac by 
wszystkie prace zostały wykonane w jak najkrótszym 
czasie. 

JSS (Job Shop Scheduling) problem należy do klasy NP.

Problem SAT 

Problem spełnialności to pytanie rachunku zdań - czy 
dla danej formuły logicznej istnieje takie podstawienie 
(wartościowanie) zmiennych zdaniowych, żeby formuła 
była prawdziwa. 

Problem spełnialności jest rozstrzygalny - można 
wypróbować wszystkich podstawień których jest 2

N

, 

gdzie N to liczba zmiennych w formule. Metoda ta ma 
więc złożoność wykładniczą.

Problem SAT, jest problemem NP-zupełnym. 

Problem plecakowy

Problem plecakowy jest jednym z 

najczęściej poruszanych problemów 
optymalizacyjnych. Nazwa 

zagadnienia pochodzi od 
maksymalizacyjnego problemu 

wyboru przedmiotów, tak by ich 
sumaryczna wartość była jak 

największa i jednocześnie mieściły się 
w plecaku. Przy podanym zbiorze 

elementów o podanej wadze i 
wartości, należy wybrać taki podzbiór 

by suma wartości była możliwie jak 
największa, a suma wag była nie 

większa od danej pojemności plecaka.

Definicja formalna: mamy do dyspozycji plecak o maksymalnej pojemności 
B oraz zbiór N elementów {x

1

,x

j

,...,x

N

}, przy czym każdy element ma 

określoną wartość c

j

 oraz wielkość w

j

.

Dyskretny problem plecakowy (ang. 0-1 knapsack problem)

formalnie problem może być zdefiniowany: 

zmaksymalizuj 

 

przy założeniach: 

 

Problem plecakowy, w którym liczba elementów danego typu jest 
ograniczona przez podaną wartość (ang. bounded knapsack problem).

Formalnie: 

zmaksymalizuj 

 

przy założeniach: 

 

Można rozważać także przypadek w którym nie ma wartości ograniczającej liczbę elementów danego typu (ang. unbounded knapsack problem).

Problem plecakowy

Problem plecakowy jest NP-trudny i nie jest dla niego 
znany algorytm wielomianowy (gdyby istniał 
oznaczałoby to, ze P=NP). Znany jest jednak algorytm 
pseudowielomianowy dla tego problemu oparty na 
programowaniu dynamicznym. 

Pojęcie redukcji

Definicja 2:
Mówimy ze B redukuje się do A, jeżeli istnieje
transformacja R, w wyniku której dla każdego 
przykładu x problemu B powstaje równoważny mu 
przykład R(x).

Problem stopu

Problemem stopu nazywamy sytuację, gdy dla 
danego algorytmu należy stwierdzić, czy program 
realizujący dany algorytm zatrzyma się. Pytanie może 
odnosić się albo do konkretnych danych wejściowych, 
albo do wszystkich możliwych danych. Jeśli program 
zatrzymuje się dla wszystkich danych, to mówimy, że 
ma własność stopu.
Problem stopu

 nie jest rozstrzygalny

, co oznacza, że 

nie istnieje uniwersalny algorytm rozstrzygający o 
innych algorytmach, czy mają własność stopu. 

Problem stopu

Do w ó d  ni er oz wi zy w aln o ci: z a ó my, z e  m a m y  d o  dy s p o zy cji

ą

ś

ł ż

 

al g oryt m  S  roz strzy g aj cy pr o bl e m  st o pu (zwr a c a  1  g dy si e

ą

 

z atrzy m uj e, 0  g dy ni e).

U yj my g o  d o  n a pis a ni a  inn e g o  pr o gr a m u:

ż

program T(P)

if S(P, P) == 1

wejdź w nieskończoną pętle

else

zakończ program

Pytani e  „czy T z atrzy m uj e  si , g dy d o st a ni e  jak o  ar g u m e nt si e bi e

ę

 

s a m e g o” pr o w a dzi d o  s prz e c z n o ci, a  wi e c  S ni e  m o e  istni e .

ś

ż

ć