如何找到這個算法的時間複雜度？

Question

int multiply(int a[],int low,int high,int modulus) 
{ 
    if(low==high) 
     return (a[low]); 
    else 
    { 
     int mid = (low+high)/2; 
     int x = multiply(a, low, mid, modulus) % modulus; 
     int y = multiply(a, mid+1, high, modulus) % modulus; 
     return ((x*y) % modulus); 
    } 
} 

它的時間複雜度是O（log n）還是O（n）？

請幫幫我。

Answer 1

您正在撥打O(N)致電multiply，其中N == high - low處於頂級通話。

E.g.爲方便起見採取N=2^K。在您遇到low==high的情況之前，您正在遞歸K深度。在每個級別，您都有2^(K-1)調用。它們加起來總共有N - 1個呼叫（1 + 2 + 4 + ... + 64 = 127）。

對於一般的N縮放行爲是相同的，你可以使用基於你函數的遞歸關係T(N) = 2 T (N/2)的Master Theorem的案例1來證明。