NTP

11. Algoritam za stepenovanje brojeva.

Treba da sracunamo y = x^n  (n je prirodan broj)
x^n = x * x * x * … * x (n cinilaca / faktora)
————————————-
double Stepen(double x, int n) {
  double y;
  int k;
  y = 1.0;
  for (k = 1; k <= n; k++)
    y = y * x;
  return y;
}
————————————-
Slozenost ovog algoritma je O(n) jer imamo petlju koja se ponavlja n puta.
x^0 = 1
x^1 = x
Ako je n paran broj, tj. n = 2k, onda je x^n = x^(2k) = (x^k)^2\
Ako je n neparan broj, tj. n = 2k + 1, onda je
x^n = x^(2k+1) = x^(2k) * x = (x^k)^2 * x
——————————————
double Stepen1(double x, double n) {
  if (n == 0)
    return 1;
  if (n == 1)
    return x;
  if (n % 2 == 0) {
    y = Stepen1(x, n/2);
return y * y;
  } else {
    y = Stepen1(x, n/2);
return y * y * x;
  }
}
——————————————–
T(n) = T(n/2) + Teta(1)
Po Master teoremi se dobije da je T(n) = Teta)log(n))