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