Witam. Jestem w trakcie tworzenia dużego typu liczbowego, który jest reprezentowany przez tablicę Dword w systemie pozycyjnym o podstawie 10^9. Mój problem dotyczy algorytmu mnożenia. Ten, który wymyśliłem, działa tak (w pseudokodzie):
tmp = 0;
while (mnożnik > 1)
{
if (mnożnik podzielny przez 2)
{ // mnożną pomnóż przez 2, mnożnik podziel na 2
mnożna <<= 1;
mnożnik >>= 1;
}
else
{
tmp += mnożna;
--mnożnik;
}
}
mnożna += tmp;
Mam pytanie dotyczące złożoności obliczeniowej tego algorytmu. Przesunięcia bitowe, dodawanie i dekrementacja działają w czasie liniowym. Porównanie zarówno w warunku pętli, jak i wewnętrznym zachodzi w czasie stałym.
Wg. moich rozważań, zakładając rozmiary obu liczb równe n, optymistyczna złożoność (mnożnik jest potęgą dwójki) wynosi O(nlg(n)). Jeśli chodzi o przypadek pesymistyczny, to w połowie przebiegów wykonywane jest dzielenie+mnożenie, a w połowie dodawanie+dekrementacja, wobec tego złożność powinna wynosić O(n/2lg(n/2) + (n/2)*n), co asymptotycznie daje O(n^2).
Teraz proszę o sprawdzenie, czy nie mylę się w szacowaniu złożoności - mam wrażenie, że mogłem się pomylić, jakoś zbyt szybki ten algorytm mi się wydaje. :D