시간 열거의 comlpexity 모든 하위 집합

Question

for (i=0;i<n;i++) 
{ 
    enumerate all subsets of size i = 2^n 
    each subset of size i takes o(nlogn) to search a solution 
    from all these solution I want to search the minimum subset of size S. 
} 

나는이 알고리즘의 복잡성을 알고 싶습니다. 2^n O(nlogn*n)=o(2^n n²) ??

당신은 n 숫자의 소트 세트의 모든 부분 집합을 반복 : 바로 당신을 이해한다면

Answer 1

.
각 하위 집합에 대해 솔루션 인 경우 O(n log n)에서 테스트합니다. (어떻게 이런 일을하는지)
이 솔루션을 모두 찾은 후에는 가장 정확한 금액이 정확히 S 인 요소를 찾고 있습니다.

작성 방법에 따라 복잡도는 O(2^n * n log n) * O(log (2^n)) = O(2^n * n^2 log n)이됩니다. O(log (2^n)) = O(n)은 최소 솔루션을 검색하기위한 것이며 최악의 경우 i=n/2 인 for 루프의 매 라운드마다이 작업을 수행하며 모든 하위 집합은 솔루션입니다.

이제는 O()과 o()을 섞으면 확실하지 않습니다.
2^n O(nlogn*n)=o(2^n n²)은 2^n O(nlog(n*n)) 인 경우에만 적합합니다.
f=O(g)은 f의 복잡도가 g의 복잡도보다 크지 않음을 의미합니다.
f=o(g)은 f의 복잡도가 g의 복잡성보다 작음을 나타냅니다.

그래서 2^n O(nlogn*n) = O(2^n n logn^2) = O(2^n n * 2 logn) = O(2^n n logn) < O(2^n n^2)

공지 사항 : O(g) = o(h) 좋은 표기 적이 없다. (대개의 경우 항상) 인 f이지만 인 경우 f != O(g) 인 함수를 찾을 것입니다. 개선

:
가 내가 알고리즘의 권리를 이해한다면, 당신은 그것을 조금 속도를 높일 수 있습니다. 원하는 하위 집합의 크기를 알고 있으므로 크기가 S 인 모든 하위 집합 만 봅니다. 최악의 경우는 S=n/2이므로 C(n,n/2) ~ 2^(n-1)은 복잡성을 줄이지 만 요소 2를 절약합니다.
또한 솔루션을 저장하고 다음 솔루션이 더 작은 지 확인할 수 있습니다. 이렇게하면 다시 검색 할 때 가장 작은 솔루션을 얻을 수 있습니다. 복잡성은 O(2^n * n log n)입니다.