這段代碼的運行時間是多少？它是n日誌還是n日誌？

Question

我已經寫了這段代碼，用分而治之的方法找到pow（a，n）。我不確定這個代碼的複雜性。它是n還是nlog n？

pow(a,n) 
{ 
    if n->1 return a 
    i<-floor(n/2) 
    j<-ceil(n/2) 
    return pow(a,i) * pow(a,j) 
} 

在這種情況下乘法的組合步驟的複雜程度是什麼？是1還是n？

Answer 1

由於每次撥打pow(a,n)都會導致約2個電話撥打pow(a,n/2)，因此大約爲O（n）。