Binäre Exponentiation - Laufzeitanalyse

Question

Aufgabe:

Binäre Exponentiation - Laufzeitanalyse.

Zu zeigen: Worstcase Laufzeit Binäre Exponentiation (rekursiv definiert) soll Ο(log(n)) sein.

Als Hinweis ist folgendes angegeben: Hinweis: Sie können zunächst eine Rekursionsgleichung T(n) = ... aufstellen und dann durch vollständige Induktion eine obere Schranke auf T(n) zeigen.

Answer 1

Aloha :)

Wenn du das als Iteration schreibst:

double power(double x, unsigned n) {
  double p= 1.0;
  while (n) {
      p*=  (n&1) ? x : 1;
      n>>= 1;
      x*=  x;
  }
  return p;
}

ist sofort klar, dass die Schleife maximal \(\lceil\log_2(n)\rceil\) Mal durchlaufen wird.