Złożoność obliczeniowa



Pobieranie 60,73 Kb.
Data16.12.2017
Rozmiar60,73 Kb.


Wprowadzenie do EiT2

2005/2006
1. Zastosowanie informatyki cz. I ( praktyczne aspekty teorii złożoności obliczeniowej, sieci neuronowe, programowanie rozproszone w sieciach komputerowych - prof. W. Greblicki)
2. Zastosowanie informatyki cz. II ( algorytmy, sztuka programowania, szeregowanie zadań, rozkrój surowca - prof. Z. Hasiewicz)

3. Zastosowanie informatyki cz. III


Poniedziałek w godz. 17.05-18.45 sala 205/C-1
27 MARZEC, 3 KWIECIEŃ, 10 KWIECIEŃ
Wtorek w godz. 17.05-18.45 sala 205/C-1
28 MARZEC, 4 KWIECIEŃ, 11 KWIECIEŃ






27 – 28 marzec 2006

03 – 04 kwiecień 2006

10 – 11 kwiecień 2006

PON

Jerzy Kotowski

Ryszard Klempous

Ewa Szlachcic

Grzegorz Mzyk

WT

Jerzy Kotowski

Ryszard Klempous

Ewa Szlachcic

Grzegorz Mzyk



Złożoność obliczeniowa

From Wikipedia


Teoria złożoności obliczeniowej to dział informatyki teoretycznej. Głównym jej celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas i pamięć, dlatego też używa się określeń "złożoność czasowa" i "złożoność pamięciowa". Pojęcie to wprowadzili J. Hartmanis i R. Stearns.

Za jednostkę złożoności pamięciowej przyjmuje się pojedyncze słowo maszyny (np. Bajt).

W przypadku złożoności czasowej nie można podać bezpośrednio jednostki czasu, np. milisekundy, bowiem nie wiadomo na jakiej maszynie dany algorytm będzie wykonywany. Dlatego też wyróżnia się, charakterystyczną dla algorytmu, operację dominującą. Liczba wykonań tej operacji jest proporcjonalna do wykonań wszystkich operacji.

Rozróżnia się dwa rodzaje złożoności:



złożoność pesymistyczna 

określa złożoność w "najgorszym" przypadku. Jeśli D oznacza zbiór wszystkich możliwych danych wejściowych, d jeden z elementów tego zbioru, a f funkcję, która dla danego d zwraca liczbę operacji, to złożoność pesymistyczna jest zdefiniowana jako:





złożoność oczekiwana 

określa złożoność średnią czyli wartość oczekiwaną zmiennej losowej f. Jeśli wszystkie dane są jednakowo prawdopodobne (z prawdopodobieństwem niezerowym) wtedy wyraża się ona wzorem:





Złożoność obliczeniowa nie jest wygodna w stosowaniu, bowiem operacja dominująca na jednym komputerze może wykonywać się błyskawicznie, na innym zaś musi być zastąpiona szeregiem instrukcji.

Dlatego też częściej stosuje się złożoność asymptotyczną, która mówi o tym jak złożoność kształtuje się dla bardzo dużych, granicznych rozmiarów danych wejściowych.


Do opisu złożoności asymptotycznej stosuje się trzy notacje:

  1. Notacja wielkie O

  2. Notacja Ω (Omega wielkie)

  3. Notacja Θ (Teta)

Niech będą dane funkcje f oraz g, których dziedziną jest zbiór liczb naturalnych, natomiast przeciwdziedziną zbiór liczb rzeczywistych dodatnich.

Notacja "Wielkie O"


Mówimy, że f jest co najwyżej rzędu g, gdy istnieją takie stałe n0 > 0, oraz c > 0, że:

Zapis: f(n) = O(g(n))

Określenia "złożoność co najwyżej O(f(n))" i "złożoność O(f(n))" są matematycznie równoważne.

Notacja "Wielkie Omega"


Mówimy, że f jest co najmniej rzędu g, gdy istnieją takie stałe n0 > 0, oraz c > 0, że:

Zapis: f(n) = Ω(g(n))


Notacja "Teta"


Mówimy, że f jest dokładnie rzędu g, gdy istnieją takie stałe n0 > 0, oraz c1 > 0 i c2 > 0, że:

Zapis: f(n) = Θ(g(n))



Można powiedzieć, że f(n) = Θ(g(n)), gdy f(n) jest jednocześnie rzędu O(g(n)) i Ω(g(n)).

Definicje algebraiczne O, o, Ω, ω, Θ


Notacja

Definicja





















W praktyce wartości stałych c, oraz c1 i c2 wpływają na efektywność algorytmu.

Najczęściej spotykane rzędy złożoności


1 stała

log2n logarytmiczna

n liniowa

nlog2n liniowo-logarytmiczna

n2 kwadratowa

n3 sześcienna

nc wielomianowa

cn wykładnicza

P, NP


Klasa P to wszystkie problemy decyzyjne, które można rozwiązać deterministycznym algorytmem o złożoności wielomianowej (polynomial time).

Klasa NP to wszystkie problemy decyzyjne, które rozwiązuje niedeterministyczny algorytm wielomianowy (non-deterministic polynomial).



©operacji.org 2017
wyślij wiadomość

    Strona główna