n位二进制置换表示的时间复杂度

Question

我已经在java中返回了下面的代码，以产生n个数字的可能的二进制表示。

public List<String> binaryRepresenation(int n){
    List<String> list = new ArrayList<>();
    if(n>0){
        permuation(n, list, "");
    }
    return list;
}

private void permuation(int n, List<String> list, String str){
    if(n==0){
        list.add(str);
    }else{
        permuation(n-1, list, str+"0");
        permuation(n-1, list, str+"1");
    }
}

对于n=3，它产生001 001 010 011 100 101 110 111组合。总体而言，该函数产生2^N种可能的表示形式。

可以说时间复杂度是n*2^n吗

Answer 1

你的分析有个小问题。正如您所注意到的，对于每个基本情况，您必须调用函数n次。但是，其中一些电话被其他基本案件分享。换句话说，您正在多次计算同一个呼叫。

这意味着，虽然复杂性肯定不能大于n*2^n，但实际上可能更低。

要计算复杂度的更好界限，可以计算对permutation函数的实际调用次数。一种方法是考虑str变量的可能值。

str将是长度小于或等于n的二进制字符串。此外，每次调用permutation函数都会收到str的唯一值。这意味着函数被调用的次数等于长度<=n的二进制字符串的数目。

这样的弦有多少根？1+2+4+...+2^n=2^(n+1)-1

因此，调用置换的次数为O(2^n)。但是每个调用都包含操作str+“0”和str+“1”。这些操作需要O(n)时间。因此，该操作的净时间复杂度为:O(n*2^n)，但原因与您最初的想法有些不同。