비트마스크와 재귀의 시간복잡도 차이

둘의 공통점은 긴 배열에서 요소들이 속했는지 아닌지 bool 개념을 이끌어낼 수 있다. 다만 이러한 요소들의 연산을 수행할 때는 시간복잡도가 차이가 난다. 비트마스크는 요소를 지정한 후 연산을 이끌어내지만, 재귀는 요소를 지정하는 과정에서 연산을 할 수 있다는 장점이 있다.

 

예를 들어 n이라는 길이에서

1) 비트마스크

for(int i=0; i<(1<<n); i++) {

    for(int j=0; j<n; j++) {

        sum += ...

    }

} 

O(N) = (2^n)*n

2) 재귀

void go(int idx, int sum) {
    if(idx == n) {

       ...

    }

    go(idx + 1, sum | sumstr[idx])

    go(idx, sum | sumstr[idx])

}

O(N) = (2^n)