如何找到这个算法的时间复杂度？

-1

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）？如何找到这个算法的时间复杂度？

请帮帮我。

来源

2013-08-06 user2656561

*你认为复杂性是什么？ – jrok

你知道[主定理]（http://en.wikipedia.org/wiki/Master_theorem）吗？尝试将其应用于您的算法。 –

尝试使用不同的n值，并绘制图表。然后看看形状 – doctorlove

您正在拨打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来证明。

来源

2013-08-06 11:37:50 TemplateRex

如何找到这个算法的时间复杂度？

回答

相关问题