我在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組合?？傮w而言，該函數產生2 ^ n種可能的表示形式?？梢钥隙ǖ卣f時間復雜度是n * 2 ^ n在2 ^ n次的情況下，針對基本情況調用該方法。為了達到每種基本情況，將調用置換方法最多n次。因此，總的上限時間復雜度為n * 2 ^ n？如果我錯了，請糾正我。我來到了基于該主題討論串置換時間復雜度這一結論字符串的置換時間復雜度。您的幫助將不勝感激。
2 回答
慕森卡
TA貢獻1806條經驗 獲得超8個贊
時間復雜度為O（2 n）。每個函數調用將兩個新的函數調用壓入堆棧，直到達到基本情況為止?？梢暬瘶?，n = 3如下所示：
________""________ / \ ___0___ ___1___ / \ / \ _00_ _01_ _10_ _11_ / \ / \ / \ / \ 000 001 010 011 100 101 110 111
這是一個具有15個節點和8個葉子的完美的二叉樹。訪問了2 n + 1個狀態，但是我們可以刪除常數并將其簡化為O（2 n）。
字符串串聯n使復雜度增加了一個倍數，但是使用StringBuilder具有固定時間push / pop或add / remove操作的或容器應消除這種情況，這表明這只是特定于您所發布代碼的實現細節，而不是算法的復雜性。一般的。
添加回答
舉報
0/150
提交
取消