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？如果我错了，请纠正我。我来到了基于该主题讨论串置换时间复杂度这一结论字符串的置换时间复杂度。您的帮助将不胜感激。

Answer 1

时间复杂度为O（2 ⁿ）。每个函数调用将两个新的函数调用压入堆栈，直到达到基本情况为止。可视化树，n = 3如下所示：

            ________""________
           /                  \
       ___0___              ___1___
      /       \            /       \
    _00_     _01_        _10_     _11_
   /    \   /    \      /    \   /    \
  000  001 010   011   100  101 110   111

这是一个具有15个节点和8个叶子的完美的二叉树。访问了2 ^{n + 1}个状态，但是我们可以删除常数并将其简化为O（2 ⁿ）。

字符串串联n使复杂度增加了一个倍数，但是使用StringBuilder具有固定时间push / pop或add / remove操作的或容器应消除这种情况，这表明这只是特定于您所发布代码的实现细节，而不是算法的复杂性。一般的。