의사 코드의 간단한 부분 2 개와 동등한

Question

내가 종이로 생각한 방식이 텍스트 북에서 제안한 의사 코드와 약간 다른 알고리즘을 구현하려고합니다. 나는 아래에있는 의사 코드의 2 개 발췌문이 각각 '포함하고'각각의 부분 집합을 생성해야 할 때 시간 복잡성의 순서에 따라 큰 차이없이 똑같은 것을 할 것이라는 것을 자신에게 확신시키고 자 노력하고있다. 나는 나를 설득 할 엄밀한 문제를 생각해 내는데 어려움을 겪고있다.

T와 A는 유한 집합 I의 하위 집합 집합입니다. 어떤 집합이나 하위 집합도 비어 있지 않으며 모든 집합에는 '개수'라는 "필드"가 있습니다.

코드 조각 한 :

For-each t in T do { 
    A_t = A intersected with the set of all non-empty subsets of t 
    For-each a in A_t do { 
    a.count++ 
    } 
} 

발췌문 두가 :

여기

For-each a in A do { 
    a.count = count(a, T) 
} 

수는 그것은 당신이 당신의 부분 집합 생성을 구현하는 방법에 따라 달라집니다 및 기능을 포함

count(a, T) { 
    c = 0 
    For-each t in T do { 
    if (t contains a) { 
     c++ 
    } 
return c 
} 

Answer 1

에 의해 정의된다. 내 생각 엔이 a가 A과 t의 부분 집합의 세트에 IFF에 a이 A_t에서와 같이 대부분의 경우, 모든 하위 집합을 생성하는 (가치되지 않고 있다는 점이다 a가 A 및 t 포함에 IFF에, 즉 a는 A_t에 두 번째 조각은 가정 두 경우 모두 (

For-each a in A do { 
    For-each t in T do { 
    if (t contains a){ 
     a.count++ 
    } 
    } 
} 

동안 a) 당신은

For-each t in T do { 
    For-each a in A do { 
    if (t contains a){ 
     a.count++ 
    } 
    } 
} 

에 첫 번째 조각을 다시 작성할 수 있습니다 모든 a은 A이고, a.count은 처음에 0으로 설정됩니다.