68800

© 2007 cih997

-jednostka złożoności czasowej - wykonanie jednej operacji dominującej

-    złożoność pesymistyczna - mówimy o niej, gdy dla ustalonego rozmiaru wejścia w charakterze miary złożoności przyjąć największą ze złożoności dla wszystkich możliwych wejść danego rozmiaru

-    złożoność oczekiwana - mówimy i niej, gdy jako miarę złożoności przyjmujemy pewną średnią złożoność dla wszystkich wejść danego rozmiaru

-    oznaczenia złożoności

+ n = | d | - rozmiar zestawu danych d + D„ - zbiór zestawu danych wejściowych rozmiaru n + r(d) - liczba operacji dominujących dla zestawu danych wejściowych d + X„ - zmienna losowa, której wartością jest r(d)

+ Pnk - rozkład prawdopodobieństwa zmiennej losowej X_n, tzn. prawdopodobieństwo, że dla danych rozmiaru n algorytm wykona k operacji dominujących (k £ 0)

-    pesymistyczna złożoność czasowa

+ W(n) = sup { r(d): d € D_n }

-    oczekiwana złożoność czasowa

+ A(n) = Zk_Ło kPnk

-    złożoność programów RAM —

-    równomierne kryterium wagowe - zakłada się w nim, że każda komenda RAM potrzebuje na jej wykonanie jednej jednostki czasu, a każdy rejestr wykorzystuje jedną jednostkę pamięci

-    logarytmiczne kryterium wagowe - oparte jest na założeniu, że koszt wykonania każdej komendy (jej waga) jest proporcjonalna do długości operandów

- logarytmiczna złożoność czasowa - suma wag logarytmicznych poszczególnych typów operandów oraz komend maszyny RAM

Operaud <7	Waga logan-tmiczna r(<7)
= 1	/(>)
i
*i	/(/)+/(c(r))+/(c(c(i)))
Komenda	Waga logarytmiczna
LOAD a	Ąa)
STORĘ 1	l(Ąo))+l{i)
STORĘ *r	l(Ąo))+Ąi)+l(c(i))
ADD a	/W 0))+/M
SUB a	l(Ąo))+Ąa)
MULT a	l(c(0))+i{a)
DIV a	/(c(0))+/(fl)
RE AD i	l(ivejscie)+l(i)
READ *i	i(wejsae)+/(/)+
WR1TE a	t(a)
JUMP b	l
JGTZ b	/Mo))
JZERO b	/Mo))
HALT	1

- logarytmiczna złożoność pamięciowa

+ Z. l(Xj), x, - największa wartość bezwzględna liczby całkowitej, która w trakcie obliczeń pojawiła się w i-tym rejestrze - 2-