[Teoria złożoności] Wyznaczenie złożoności dzelenia

[PiotrWP]

Kod: Zaznacz cały

function divide(x,y)
Wejście : dwie n - bitowe liczby całkowite x i y, y  >= 1
Wyjście : iloraz oraz reszta z dzielenia x przez y 

if x = 0 : (q,r) = (0,0)
(q,r) = divide(floor(x/2),y)
q = 2q, r = 2r
if x jest nieparzyste : r = r + 1
if r >= y : r = r - y, q = q + 1
return (q,r)

Zakładamy że

Kod: Zaznacz cały

r = r - y

ma czas \(\displaystyle{ O(n)}\) (tak jest przyjmowane w źródle z którego pochodzi zadanie) a reszta pojedynczych operacji ma \(\displaystyle{ O(1)}\). Po każdym podzieleniu \(\displaystyle{ x}\) przez dwa zmniejsza się ilość bitów o 1, czyli algorytm zakończy się po \(\displaystyle{ n}\) wywołaniach rekurencyjnych. A w każdym z nich mamy \(\displaystyle{ O(n) + O(1) = O(n)}\).Czyli całkowita złożoność to \(\displaystyle{ O(n^2)}\) co zgadza się z odpowiedzią.

Inne podejście
\(\displaystyle{ T(n) = \begin{cases} O(1) , n \le 1\\ T\left(\frac{n}{2}\right) + O(n), n > 1 \end{cases}}\)

Korzystając z tw. o rekurencji uniwersalnej mamy \(\displaystyle{ g(n) = n ^{\log_2 1} = 1}\)
\(\displaystyle{ g(n)}\) jest wielomianowo mniejszy od \(\displaystyle{ f(n)}\) więc \(\displaystyle{ T(n) = \Theta(n)}\)

Skąd ta różnica ?

[Dasio11]

Inne podejście
\(\displaystyle{ T(n) = \begin{cases} O(1) , n \le 1\\ T\left(\frac{n}{2}\right) + O(n), n > 1 \end{cases}}\)

Jeśli \(\displaystyle{ n}\) oznacza liczbę bitów, to chyba raczej \(\displaystyle{ T(n) = T(n-1) + \mathcal{O}(n)}\) ?

[PiotrWP]

Chyba tak. Czyli z tw. o rekurencji uniwersalnej tego nie zrobię ?

[Dasio11]

No nie.