http://users.eecs.northwestern.edu/~dda902/336/hw4-sol.pdf Problem 2.31 To jest zadanie 2 http://ii.yebood.com/viewtopic.php?p=21280#21280
a) W wektorze pamiętamy pierwszą kolumnę oraz pierwszy wiersz bez pierwszego wyrazu. Wektor ten ma rozmiar 2n - 1, więc dodawanie dwóch takich wektorów mamy w O(n).
b) Macierz Toeplitza ma następującą postać blokową:
\displaystyle T = \left[ \matrix{A & B\\
C & A} \right]
Zadanie polega na pomnożeniu macierzy T przez wektor blokowy \displaystyle T = \left[ \matrix{x \\
y} \right] w czasie mniejszym niż n^2.
Korzystając z dwóch (wzajemnie dualnych) obserwacji:
Ax = A(x + y - y) = A(x+y) - Ay
Ay = A(x + y - x) = A(x+y) - Ax
mamy:
T = \left[ \matrix{A & B\\
C & A} \right] \left[ \matrix{x \\
y} \right]
= \left[ \matrix{Ax + By\\
Cx + Ay} \right]
= \left[ \matrix{A(x+y)-Ay + By\\
Cx + Ay} \right]
= \left[ \matrix{A(x+y)+(B - A)y\\
Cx + Ay} \right]
= \left[ \matrix{A(x+y)+(B - A)y\\
Cx + A(x+y) - Ax } \right]
= \left[ \matrix{A(x+y)+(B - A)y\\
A(x+y) + (C-A)x} \right].
I zauważamy, że złożoność czasowa to T(n) = 3 T(n/2) + O(n) gdzie O(n) zamyka sumę liniowych czasów wszystkich dodawań.
Rozwiązując typowe równanie rekurencyjne mamy T(n) = O(n^{log_2 3}) < O(n^2).