java - 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

其中 2^n 次为基本情况调用该方法。为了达到每个基本情况，它最多调用排列方法n次。

所以总体上界时间复杂度是 n*2^n？如果我错了，请纠正我。我根据本帖 Time Complexity of Permutations of a String 中讨论的字符串置换时间复杂度得出了这个结论。 .非常感谢您的帮助。

Answer 1

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

这意味着虽然复杂度绝对不能大于 n * 2 ^ n，但实际上可能会更低。

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

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

这样的字符串有多少个？ 1 + 2 + 4 + ... + 2 ^ n = 2 ^ (n + 1) - 1

因此，调用permutation 的次数是O(2^n)。 但是每次调用都包含操作 str + "0" 和 str + "1"。这些操作需要 O(n) 时间。因此，该操作的净时间复杂度为:O(n * 2^n)，但原因与您原先想象的有所不同。