große O - Rekursion anstelle von Multiplikation - Java, Rekursion, Big-O

Arbeiten an einer Methode zum Ersetzen der Multiplikation.

public static int mult(int num, int repeat){
if (repeat == 0) return 0;
if (repeat == 1) return num;
return num + mult(num, repeat - 1);
}

In Bezug auf die zeitliche und räumliche Komplexität wäre dies O (k) Zeit, in der k die ist wiederholen und O (1) Raum?

Antworten:

Es ist O (K) Zeit, da Sie diese Funktion einmal pro aufrufen repeat und jeder Anruf ist O (1). Es ist jedoch auch O (k) Raum, in dem Sie k Stapelrahmen haben, bevor Sie die Beendigungsbedingung erreichen (in Ermangelung einer Optimierung der Endanruf-Rekursion).