算法合集之樹的枚舉-資料下載頁
2025-10-07 20:32本頁面
【正文】 相似之處。 比如說：為了使 2021成為比它小，但又與它相差最少的自然數(shù)： 2021 1999 1000 ? 類似地 , 再看一個有向樹變換的例子 : 刪除結(jié)點 ， 使子樹變小 將后面的子樹重組 （ 最大化 ） 變換完成 ? 我們先從后向前找到一個待刪除結(jié)點，刪除它之后，然后對其它子樹進行了一定的變換（類似于上面把 0變成為 9的過程），確保了整棵樹變小的程度最小，從而得到了序列中的下一棵有向樹。 ? 以上介紹的算法可以實現(xiàn)給定深度 d，結(jié)點數(shù) n，按照從大到小的順序變換生成所有形態(tài)的有向樹。算法中涉及的樹的復制，以及遍歷等，復雜度均為 O（ n），并且在樹的生成過程中完全沒有重復生成，所以整個算法的耗時主要與不同形態(tài)樹的總數(shù)有關。 ? 該算法最直接的應用是“無根樹”問題。下表可以作為算法時間復雜度的直觀參考。 N 11 12 13 14 15 16 17 18 19 20構(gòu)造用時 0. 0 5 0. 0 5 0. 1 1 0. 1 6 0. 4 9 1. 2 1 3. 1 9 8. 5 2 23. 0 8 62. 9 1搜索用時 0. 2 7 0. 7 1 2. 0 9 6. 0 4 17. 6 9 51. 9 2 15 2. 2 0 我們可以用按照枚舉算法編寫的生成程序與搜索算法作一個比較（測試環(huán)境： PIII 500MHz， 192Mb RAM， Borland Pascal ，用時單位： s）：
教學課件相關推薦
鄂ICP備17016276號-1