我知道遍历大小为n的集合的所有子集是一个性能噩梦,需要O(2^n)时间。
那么遍历大小为k (对于(0 <= k <= n))的所有子集呢? 这是个性能噩梦吗? 我知道有(n, k) = n! / k! (n - k)! 种可能性。如果k非常接近0或非常接近n,这个数字就很小。
在n和k方面,最坏情况的表现如何?除了O(n! / k! (n - k)!)之外,还有更简单的说法吗?这是否渐进地小于O(n!)或相同?
那么遍历大小为k (对于(0 <= k <= n))的所有子集呢? 这是个性能噩梦吗? 我知道有(n, k) = n! / k! (n - k)! 种可能性。如果k非常接近0或非常接近n,这个数字就很小。
在n和k方面,最坏情况的表现如何?除了O(n! / k! (n - k)!)之外,还有更简单的说法吗?这是否渐进地小于O(n!)或相同?
n
和k
的值。你在寻找什么样的答案? - shx2