Laufzeitkomplexität dieses Algorithmus?

Question

Gegeben a und b, ich werde gebeten, a^b mit einer Laufzeit schneller als O (b) zu berechnen. Ich kam mit:

if(b == 1) return a; 
if(b % 2 == 0) 
    return findExp(a,b/2) * findExp(a,b/2); 
else 
    return findExp(a,(b/2)+1) * findExp(a,b/2); 

Meine Frage ist, ist die Laufzeitkomplexität dieses Algorithmus logarithmischer Zeit oder Polynom Zeit?

Answer 1

Ihr Algorithmus ist O (b) nicht logarithmisch.

In diesem Teil des Codes return findExp(a,b/2) * findExp(a,b/2); rufen Sie die gleiche Funktion, die den gleichen Wert zweimal zurückgibt. Grundsätzlich verbringen Sie redundante Zeit für den zweiten Anruf.

Mathematisch, wenn T (b) die Zeit darstellt, die für a^b gemäß Ihrem Algorithmus erforderlich ist, ist es T(b) = T(b/2) + T(b/2), wobei jeder Ausdruck jedem Aufruf entspricht. T(b) = 2.T(b/2). Lösen Sie diese Wiederholung und Sie erhalten T (b) in der Reihenfolge von b.

Um es logarithmisch zu machen, verhindern Sie einfach diesen redundanten Aufruf, indem Sie den Wert in einer Variablen speichern.

Der bearbeitete Code:

if(b == 1) return a; 
if(b % 2 == 0) 
    int x = findExp(a,b/2); 
    return x*x; 
else 
    int x = findExp(a,b/2); 
    return a*x*x; 

Jetzt T(b) = T(b/2) da Sie anrufen findExp (a, b/2) nur einmal (entweder in if oder teilweise else Teil).

Dies gibt Ihnen O(log(b)) Algorithmus

Wenn Sie testen wollen es, den Code und die von mir für einige große b erwähnten einen laufen, lassen Sie uns b = 1000000000 sagen und die Zeiten genommen Kontrast.

Answer 2

Es ist O (log (b)), also ist es logarithmisch.