Złożoność czasowa, zależność czasu realizacji zadania od rozmiaru zadania

0

Witam. Niżej mam napisany algorytm odwrotności modulo. Potrzebuje jeszcze:
a) Oszacować złożoność czasową
b )Sporządzić wykres zależności czasu realizacji zadania od rozmiaru zadania
(liczenie kroków lub bezpośredni pomiar).

Pomoże ktoś coś ? Jak się do tego zabrać ?
Z góry dzięki :)

#include <iostream>

using namespace std;

int main()
{
  int a,b,u,w,x,z,q;

  cin >> a >> b;
  u = 1; w = a;
  x = 0; z = b;
  while(w)
  {
    if(w < z)
    {
      q = u; u = x; x = q;
      q = w; w = z; z = q;
    }
    q = w / z;
    u -= q * x;
    w -= q * z;
  }
  if(z == 1)
  {
    if(x < 0) x += b;
    cout << x << endl;
  }
  else cout << "BRAK\n";
  return 0;
}
0

Sam sobie odpowiem:), tak, to właśnie liczy; nie wiem czy Oparłeś to o Extended Euclidean Algorithm, ciężko porześledzić Twój kod:) (ale wtedy powinien wyglądać jakoś tak). Złożoność tak policzonej odwrotności jest O(log(n)^2), bo: log(n) + log(n) z algorytmu euklidesa.

1 użytkowników online, w tym zalogowanych: 0, gości: 1