złożoność Benny: Podaj równanie rekurencyjne na liczbę porównań T(n) między elementami tablicy o n elementach. Korzystając z odpowiedniego twierdzenia, wyznacz asymptotyczną złożoność T(n). Dla uproszczenia przyjmij, że n=2^k, dla pewnego naturalnego k.

g: Jeżeli każdy z każdym to T(n)=n(n−1)/2, czyli złożoność jest typu wielomianowego n². Konkretny algorytm (np sortowania) nie musi porównywać wszystkiego, tak więc złożoność zależy od algorytmu, a nie tylko od rozmiaru danych.

Benny: @g, ale tu chodzi o równanie rekurencyjne. Chyba, że ja źle rozumiem treść.

Pytający: T(0) = 0 T(1) = 0+0 = 0 T(2) = 0+1 = 1 T(3) = 1+2 = 3 T(4) = 3+3 = 6 T(5) = 6+4 = 10 T(n) = T(n−1)+(n−1) T(n) = T(n−1)+(n−1) = T(n−2)+(n−2)+(n−1) = T(0)+(n−n)+(n−(n−1))+...+(n−2)+(n−1) =

	1+(n−1)		n(n−1)
∑m=1n−1m =		*(n−1−1+1) =
	2		2

Masz wzór rekurencyjny, ale wykorzystania "odpowiedniego twierdzenia" nie mam.

Benny:

	n
Gdybyśmy zapisali T(n)=aT(		)+f(n) to można skorzystać z rekurencji uniwersalnej.
	b

Benny:

	n		n(n−1)
T(n)=T(		)+		?
	2		4

Benny: czyli T(n)=θ(n²log₂n)?

Pytający: Wzór z 15:53 jest zły.

	n		n		n		n(n−1)		n   n   ( −1) 2   2
T(n) = T(		) + T(n)−T(		) = T(		) +		−		=
	2		2		2		2		2

	n		n(3n−2)
T(		) +
	2		8

Benny: Tak wiem, z pośpiechu to zrobiłem

Pytający: I T(n)=θ(n²), więc jeśli wyjdzie to inaczej, to źle (jakkolwiek to liczysz).

Benny: Tak mi też wyszło.

Benny: Chociaż chyba wyszło mi nlog₂n

Benny: n²log₂n