n位二进制排列表示的时间复杂度 [英] Time Complexity for binary permutation representation of n bits

问题描述

我已经在Java中返回了以下代码，以生成可能的n位二进制表示形式.

I have return a below code in java to produce the possible binary representation of n digits.

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种可能的表示形式.

For n=3, it produces 001 001 010 011 100 101 110 111 combinations. Overall this function produces 2^n possible representations.

可以肯定地说时间复杂度是n * 2 ^ n

Is it safe to say the time complexity is n * 2^n

在2 ^ n次的情况下，对于基本情况将调用该方法.为了达到每种基本情况，它最多需要调用n次排列方法.

Where 2^n time the method is called for base cases. In order to reach the each base case, it would have called the permutation method for maximum of n times.

那么总的上界时间复杂度是n * 2 ^ n吗?如果我错了，请纠正我.我基于此线程中讨论的字符串排列时间复杂度得出了这个结论时间复杂度字符串的排列.非常感谢您的帮助.

So overall upper bound time complexity is n*2^n? Kindly correct me if i am wrong. I came to this conclusion based on the string permutation time complexity discussed in this thread Time Complexity of Permutations of a String . Your help will be much appreciated.

推荐答案

您的分析存在一个小问题.如您所见，对于每种基本情况，您必须调用该函数n次.但是，其中一些调用正在由其他基本案例共享.换句话说，您多次计算同一呼叫.

There is a small problem with your analysis. As you noticed, for each base case you have to call the function n times. But, some of those calls are being shared by other base cases. In other words, you are counting the same call multiple times.

这意味着尽管复杂度绝对不能大于 n * 2 ^ n ，但实际上可能更低.

This means that while the complexity definitely can't be greater than n * 2 ^ n, it might actually be lower.

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

To calculate a better bound on the complexity, you can count the actual number of calls to the permutation function. One way to do that is to consider the possible values of the str variable.

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

str will be a binary string of length less than or equal to n. Also, each call to the permutation function receives a unique value of str. This implies that the number of times the function is called is equal to the number of binary strings of length <= n.

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

How many such strings are there? 1 + 2 + 4 + ... + 2 ^ n = 2 ^ (n + 1) - 1

因此，置换的调用次数为 O(2 ^ n).但是每个调用都包含操作 str +"0" 和 str +"1" .这些操作花费 O(n)时间.因此，该操作的净时间复杂度为: O(n * 2 ^ n)，但是由于与您最初想像的原因有所不同.

So, the number of times permutation is called is O(2^n). But each call includes the operations str + "0" and str + "1". These operations take O(n) time. So, the net time complexity of the operation is: O(n * 2^n) but for somewhat different reasons than you originally thought.

这篇关于n位二进制排列表示的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！