搜索的時間復雜度:O(答案總數 * 構造每個答案的時間) 舉例:Subsets問題,求所有的子集。子集個數一共 2^n,每個集合的平均長度是 O(n) 的,所以時間復雜度為 O(n * 2^n),同理 Permutations 問題的時間復雜度為:O(n * n!)
動態規劃的時間復雜度:O(狀態總數 * 計算每個狀態的時間復雜度) 舉例:triangle,數字三角形的最短路徑,狀態總數約 O(n^2) 個,計算每個狀態的時間復雜度為 O(1)——就是求一下 min。所以總的時間復雜度為 O(n^2)
用分治法解決二叉樹問題的時間復雜度:O(二叉樹節點個數 * 每個節點的計算時間) 舉例:二叉樹最大深度。二叉樹節點個數為 N,每個節點上的計算時間為 O(1)??偟臅r間復雜度為 O(N)
新聞熱點
疑難解答