c++ - 如何找到该算法的时间复杂度？

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在顶级调用中。

例如N=2^K，为方便起见。在K遇到low==high. 在每个级别，您都有2^(K-1)电话。它们加起来总共N - 1调用了 (1 + 2 + 4 + ... + 64 = 127)。

一般来说N，缩放行为是相同的，您可以根据函数的递归关系使用主定理的案例 1 来证明这一点。T(N) = 2 T (N / 2)