쉽게 배우는 알고리즘-02 연습문제

1. 어떤 알고리즘의 크기 n인 모두 가능한 입력의 수는 n!이다. 충분히 큰 n에 대하여 "항상" 다음의 성질이 성립한다.

입력 중 100개에 대해서 알고리즘은 n^2에 비례하는 시간이 든다 입력 중 100개에 대해서 알고리즘은 n에 비례하는 시간이 든디 이외의 모든 입력에 대해 알고리즘은 nlogn에 비례하는 시간이 든다

Best case : n

Worst case : n^2

Average case : nlogn

 

이 알고리즘의 수행시간이 다음과 같다고 주장하려한다. OX 및 이유

1) O(n^2)이다. : O, O는 점근적 상한 f(n)<=g(n)이므로 가능

2) 최악의 경우 O(n^2)이다 : O

3) 최악의 경우 Θ(n^2)이다 : O

4) 평균적인 경우 Θ(nlongn)이다 : O

 

2. 수행시간 n을 기준으로 어떤 함수에 비례하는 가? 

Θ(n^3)

 

3. 관계가 있는 것 끼리 서로 연결하시오. 하나에 여러개가 될 수도 있다. 

1. A, B, C, D

2. A, B, C, D

3. B, D, E, F

4. B, D

5. B, D, E, F

6. B, E 

7. B, E

 

4. 어떤 알고리즘이 단 두개의 입력에 대해서만 n^2에 비례하는 시간이 소요되고 나머지 모든 케이스에 대해서는 nlogn에 비례하는 시간이 소요된다. 다음 물음에 OX로 답하시오.

Worst case : n^2

Average case : nlogn

1. '이 알고리즘은 점근적 수행 시간은 Θ(n^2) 이다'라고 말할 수 있는가? X Θ(nlongn)

2. '이 알고리즘은 점근적 수행 시간은 O(n^2) 이다'라고 말할 수 있는가? O

3. '이 알고리즘은 최악의 경우 수행 시간은 O(n^2) 이다'라고 말할 수 있는가? O

4. '알고리즘의 수행 시간이 최악의 경우 Θ(n^2)'이라는 말과 '알고리즘의 수행 시간이 O(n^2)' 이라는 말은 같은 뜻인가? O

 

5, 2절에서 배운 세 가지 점근적 표기(O, Θ, Ω) 중에서 다음에 해당하는 것을 각각 말해보시오.

1. 상한의 개념이 포함되어 있는 것은?

> O

2. 하한의 개념이 포함되어 있는 것은?

> Ω