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 .

ś

ż

ć