登录
  • #刷题

Combinations和Subset时间复杂度比较[Leetcode]

mattsun
23692
20
Leetcode上两道题目, Combinations和Subsets, 时间复杂度分别是多少?

我觉得Combinations的递归方法复杂度是O(n!)而Subsets的复杂度也是O(n!)

理由: Combinations的递归方法每次递归要检查n个元素(或者n-1个,n-2个..),总共要做n!次

而Subsets其实就是做2^n次Combinations来获取Subsets, 因此复杂度是O(2^n * n!) = O(n!)

但是根据在这里看到的解: https://github.com/soulmachine/leetcode

Combinations的时间复杂度是O(n!)而Subsets的时间复杂度是O(2^n),

可是O(n!)>O(2^n),一个子问题(Combinations)的时间复杂度是不可能大于主问题的(Subsets)

另外还有一种意见:https://oj.leetcode.com/discuss/24964/o-2-n-or-o-n?show=25008#a25008

这里的stellari说Combinations的时间复杂度不是O(n!),而是远远小于O(2^n)<O(n!)

有什么建议吗?
20条回复
热度排序

发表回复