計算能力集算法分析

我有兩種算法來計算一組集合的所有子集。例如，{1, 2, 3} =>功率設置爲{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}計算能力集算法分析

一種算法是使用迭代求解; i（outer for loop）爲nums陣列運行，j運行至目前爲止計算的所有子集，並繼續將ith號碼添加到先前計算的子集。

static List<List<Integer>> subsetItr(int[] nums) { 
    List<List<Integer>> subsets = new LinkedList<>(); 
    subsets.add(new LinkedList<>()); 
    for (int i = 0; i < nums.length; i++) { 
     int size = subsets.size(); 
     for (int j = 0; j < size; j++) { 
      List<Integer> current = new LinkedList<>(subsets.get(j)); 
      current.add(nums[i]); 
      subsets.add(current); 
     } 
    } 
    return subsets; 
}

因此，鑑於此，我想確保我正確分析運行時間。假設n是nums數組的大小，那麼外部for循環是O(n)。 Inner for循環的每個迭代都按指數倍增長，因此內循環爲O(2^n)。最終的複雜性是O(n*2^n)。這是否比下面的遞歸解決方案慢O(2^n)？

static List<List<Integer>> subsets(int[] nums) { 
    List<Integer> current = new LinkedList<>(); 
    _subsets(nums, 0, current, ret); 
    return ret; 
} 

static void _subsets(int[] nums, int pos, List<Integer> current) { 
    if (pos == nums.length) { 
     System.out.println(current); 
     return; 
    } 
    current.add(nums[pos]); 
    _subsets(nums, pos + 1, current, ret); 
    current.remove(current.size() - 1); 
    _subsets(nums, pos + 1, current, ret); 
}

來源

2017-07-15 codereviewanskquestions

您是否嘗試過測量它？ – fafl

我做了..如果我實際運行該程序，那麼迭代解決方案需要更長的時間，但我想確保我的運行時分析是正確的。看起來像我對迭代解決方案的分析是不正確的，儘管下面的答案是。 – codereviewanskquestions

它們是相同的，無論是複雜爲O（2^n）的，因爲你的第一個算法的複雜度爲O（1 + 2 + 2^2 + ... + 2 ^（N-1 ））= O（2^n），你不能只是查看內部循環的所有複雜性，你必須分別計算每一個，然後像我一樣添加它們，希望這篇文章能幫助你！

來源

2017-07-15 23:50:50 codecrazer

計算能力集算法分析

回答

相關問題