这个递归函数的时间复杂度是多少？

Question

void rec( char s1[], char s2[], int i,  map< char, int > m1, map< char, int > m2 ) {
    if ( i == n ){
        return;
    }
    rec( s1, s2, i+1, m1, m2 );
    m1[ s1[ i ] ]--;
    if ( m1[ s1[ i ] ] == 0 ){
        m1.erase( s1[ i ] );
    }
    m2[ s2[ i ] ]--;
    if ( m2[ s2[ i ] ] == 0 ){
        m2.erase( s2[ i ] );
    }
    m2[ s1[ i ] ]++;
    m1[ s2[ i ] ]++;
    if ( max( ( m1.size() ), ( m2.size() ) ) < mn ){
        mn = max( ( m1.size() ), ( m2.size() ) );
    }
    rec( s1, s2, i+1, m1, m2 );
}

mn 是一个全局变量。这个递归函数的时间复杂度是多少？假设 n (<=20) 作为输入 already.n 也是全局的。并且还假设它是从 main 调用的，

rec(s1,s2,0,m1,m2);

我的猜测是 O(logn * 2^n)。正确吗？

Answer 1

rec调用了自己两次，所以如果N == (n-i)，我们可以把调用流程想象成高度为N的二进制三：rec会被恰好调用2^(N+1)-1 次。

rec 还调用其他函数，如 map<...>::size、map<...>::operator[]、map<...>::erase 等。这些函数中最昂贵的应该是 O(log M)，其中M 是地图的大小。它们是按顺序调用的，因此对于 rec.

的每次调用，我们只需要考虑这些操作中最昂贵的操作

因此最终的复杂度将是 O(2^N * log M)，N == (n-i) 和 M == max size of m1 and of m2

这个递归函数的时间复杂度是多少？

What is the Time complexity of this recursive function?

c++

recursion

time-complexity