0/1 배낭의 효율성에 대한 질문?

Question

로 배낭은

빠른 아무리 큰 W W 인 경우

큰 메모리가 필요할 수있다 배낭

1. 선형 시간 복잡도에 대한 O의 시간 복잡도 (NW)

   가 없다 큰

2. W가 n에 정비례하면 시간 복잡도는 O (n^2)가됩니다.
3. 위의 어느 것도 없습니다.

위 중 하나가 사실입니까? I는 2, 3, 4가 정확하다고 생각

Answer 1

오 (NW)를 배낭 문제 대 - 시간 알고리즘은 단지 숫자 응답 값과 Θ (NW) 메모리는 경우가 발생하는 경우 Θ (n)이 메모리를 사용 실제 응답을 생성합니다.

1. 선형 시간의 정의는 무엇인가
   이를 감안할 때, 여기에 몇 가지 힌트는? O (nW) 선형 시간입니까?
2. 이것은 "빠름"의 정의에 따라 다릅니다. 교사/교수는 표준 용어가 아니기 때문에 여기에서 의미하는 바에 대한 세부 정보를 입력 할 수 있습니다.
3. 위에서 설명한 내용을 바탕으로 생각하면 어떻습니까?
4. O (nW)에 W = n을 대입하십시오. 너 뭐 돌아온거야?

희망이 있습니다.