-1
Ich habe diesen Code geschrieben, um pow (a, n) mit der Divide and Conquer-Methode zu finden. Ich bin mir nicht sicher über die große Komplexität dieses Codes. Ist es n oder nlog n?Was wird die Laufzeit dieses Codes sein? Ist es n log n oder n?
pow(a,n)
{
if n->1 return a
i<-floor(n/2)
j<-ceil(n/2)
return pow(a,i) * pow(a,j)
}
Auch was wird Komplexität des Kombinationsschrittes sein, der in diesem Fall Multiplikation ist? ist es 1 oder n?
bedeutet das nicht, dass es Probleme in n/2 teilt, dh log n Ebenen und auf jeder Ebene Arbeit ist n/2. was macht es nlogn? –
Betrachte die Anzahl der Aufrufe, wenn du p (1,8) hast: p (1,4) * p (1,4) dann p (1,2) * p (1,2) * p (1,2) * p (1,2) dann p (1,1) * p (1,1) * p (1,1) * p (1,1) * p (1,1) * p (1,1) * p (1,1) * p (1,1). Die Gesamtzahl der Aufrufe ist 1 + 2 + 4 + 8 = 15. – jq170727
Die Arbeit auf jeder Ebene ist nicht n/2, da Sie nur O (1) Arbeit pro Aufruf machen. – templatetypedef