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

Odpowiedz Nowy wątek
2019-02-10 18:10
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;
}
Czy to jest to samo co tzw. modular multiplicative inverse? https://en.wikipedia.org/wiki/Modular_multiplicative_inverse - lion137 2019-02-10 18:59

Pozostało 580 znaków

2019-02-10 20:44
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.


edytowany 1x, ostatnio: lion137, 2019-02-11 12:23
TL;DR co oznacza "n" w tej złożoności? - vpiotr 2019-02-11 09:14
To jest n z linka do githuba, który podrzuciłem. U niego jest to jedna z liczb czytanych, chyba b - nie pamiętam. - lion137 2019-02-11 12:22

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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