Rzad zlozonosci obliczeniowej: symbole O, Teta, Omega

qer1@o2.pl - 21 Paź 2003, 15:20

Mam problem z dokladnym zrozumieniem oznaczen O, Teta, Omega.
Na pewno tymi symbolami okresla sie *rzad* zlozonosci -
a nie dokladna zlozonosc obliczeniowa.

Pyt 1: Czy istnieje jakas konwencja do oznaczania *dokladnej*
zlozonosci obliczeniowej? (IMHO nie)

Wracajac do tych trzech symboli, matematycznie jest tak:

Zapis f(n) = O(g(n)), oznacza, ze f jest co najwyzej rzedu g (od pewnego n).

Zapis f(n) = Teta(g(n)), ze f jest tego samego rzedu co g.

Zapis f(n) = Omega(g(n)), ze f jest rzedu co najmniej g (od pewnego n).

Pyt 2: jak to sie ma do danych wejsciowych?
Slyszalem interpretacje, ze O(n) to zlozonosc pesymistyczna, Teta jest uzywana,
jesli zlozonosc jest niezalezna od danych, a Omega to zlozonosc przy danych
optymistycznych. Ale cos mi tu nie gra.

Pyt 3: Dlaczego "defaultowo" stosuje sie O() ?

Prosze o odpowiedz na pytania a nie obok :)
Przyklady uzycia symboli mile widziane.

Pozdr.
Piotrek

Wojciech Mula - 21 Paź 2003, 15:56

Tak. Można podawać złożoność obliczeniową algorytmu jako dokładną liczbę
pewnych operacji wykonywanych przez komputer. Ale wówczas ta złożoność zależy
od implementacji, języka programowania, komputera itd. Poza tym ciężko się to
liczy i w istocie sama liczba, np. wykonanych dodawań, nic nam nie mówi o
"jakości" algorytmu. Samo oszacowanie ilościowe może pomóc w lokalizacji
wąskich gardeł programu, ale to jest już lokalne dla danej implementacji
jakiegoś algorytmu.

Interpretacja złożoności O jest następująca. Gdy ilość danych wejściowych n
przekorczy n0, wóczas wartości funkcji f *dąży do* c*g(n) (c to pewna dodatnia
stała), ale nigdy nie jest większa (f(n) <= cg(n)). Innymi słowy dla pewnego
konkretnego nn0, f(n) może być dokładnie równe cg(n), ale nigdy większe, zaś w
sprzyjających warunkach może być mniejsza. Tak więc zakłada się najgorszy
przypadek, a potem można się miło rozczarować. :-)

Notacji Omega to dolne oszacowanie (f(n) = cg(n)) -- złożoność nie będzie
mniejsza niż cg(n), ale może być dowolnie większa.

Notacja Theta to taka średnia, najprościej rzecz ujmując.

Wojtek

qer1@o2.pl - 21 Paź 2003, 16:15

To wszystko prawda, ale to juz wiem i nie o to pytalem.
Pytanie jest, czy istnieje jakas literka, symbol, ktorym zwykle oznacza
sie dokladna zlozonosc. Nie mialem jeszcze 'analizy algorytmow' i nie wiem.

Problem w tym, ze wszyscy wiedza, ze gdzies dzwoni,
ale nikt nie wie dokladnie gdzie...

Pozdr.
Piotrek

Marcin 'Qrczak' Kowalczyk - 21 Paź 2003, 17:15

Nie. Takie pojęcie trudno zdefiniować: o ile przy rzędzie złożoności
wystarczy się umówić, które operacje uznajemy, że są wykonywane
w czasie stałym, więc sprawa jest dość jednoznaczna, o tyle przy
"dokładnej" złożoności trzeba by nadać wagi poszczególnym operacjom
i umówić się co do najmniejszego szczegółu zapisania algorytmu,
więc nie można oceniać złożoności danego algorytmu "w ogóle" inaczej
niż przez rząd wzrostu.

Pawel Kierski - 22 Paź 2003, 02:43

[...]

  Właśnie zauważyłem, że też mi coś nie gra 8-)
  Dokładniej rzecz biorąc dla QuickSorta. Niemal wszędzie widziałem,
że O(n) = n log n, a to nieprawda dla najgorszego przypadku (sortowania
posortowanej tablicy z wyborem pierwszego elementu do porównań), gdy
złożoność jest n^2. Czyli powinno być O(n) = n^2, Theta(n) = c1 n log n
i Omega(n) = c2 n log n, c1 c2.

  Pewnie z tego samego powodu, dla którego mosty projektuje się
z zapasem obciążenia - lepiej się miło rozczarować 8-)

Jarek Kucypera - 22 Paź 2003, 06:32

Bo jeszcze rozróżnia się złożoność średnią i pesymistyczną.
I rzeczywiście złożoność pesymistyczna jest tu jak piszes,
ale nie ma sesnu odrzucać całego algorytmu, jeśli w większości
przypadków będzie liczył w czasie nlogn.

J.K.

Piotr Wyderski - 22 Paź 2003, 07:46

wiem.

Tak, T(n), gdzie n oznacza dlugosc slowa wejsciowego, a T(n)
jest funkcja przyporzadkowujaca jej liczbe krokow koniecznych
do wykonania. Nie stosuje sie jej jednak zbyt czesto, bo w analizie
algorytmow malo kogo interesuje staly czynnik zawarty w funkcji
kosztu, gdyz na podstawie lematu o przyspieszaniu mozna go
zieniac w dowolnym stopniu.

    Pozdrawiam
    Piotr Wyderski

Piotr Wyderski - 22 Paź 2003, 08:00

To jest zlozonosc OCZEKIWANA w przypadku srednim dla
danych losowanych z rozkladem jednostajnym, a nie zlozonosc
pesymistyczna tego algorytmu. Istnieje jednak implementacja
quicksort majaca pesymistyczna zlozonosc O(n log n), ale niestety
czynnik staly tej metody jest duzy.

I to jest fakt: zlozonosc _pesymistyczna_.

NIE. Omega(n) = n log n. :-) Po to m.in. wlasnie wymyslono notacje
asymptotyczna, aby _nie pisac_ stalych multiplikatywnych, wiec nie
wiem co u Ciebie robia te literki c.

Herezja! :-) Popatrz na definicje Theta(.), w jaki sposob
chcesz ja zdefiniowac, gdy O(.) i Omega(.) nie sa takie
same?! Ten algorytm NIE MA thety. :-)

    Pozdrawiam
    Piotr Wyderski

Piotr Wyderski - 22 Paź 2003, 08:14

Bo zwykle nie ma potrzeby liczyc czynnika stalego.

Tak, T(n)=...

Zgadza sie.

Niezupelnie, O znaczy "tyle operacji _wystarczy_ do rozwiazania
kazdego przypadku". To niekoniecznie oznacza zlozonosc pesymistyczna.

Tez niezupelnie, "tyle operacji _potrzeba_ do rozwiazania kazdego
przypadku".
Zlozonosc dla danych optymistycznych moze byc mniejsza niz oszacowanie
Omega, bo przypadek optymistyczny nie jest kazdym przypadkiem. :-)

I dobrze Ci nie gra, bo to nieprawda. :-) Theta(n) oznacza, ze
tyle operacji _potrzeba i wystarcza_. W szczczegolnosci Theta
nie oznacza "niezaleznosci zlozonosci od danych", bo to zachodzi
tylko dla:

a) algorytmow dzialajacych w czasie stalym;
b) algorytmow pseudowielomianowych.

:-)

Bo jesli znamy dolne ograniczenie problemu (Omega), to zwykle
interesuje nas czy nasz algorytm jest w stanie je osiagnac,
tj. ile operacji mu wystarcza, czyli jakie ma O().

    Pozdrawiam
    Piotr Wyderski