알고리즘 과제 #1

 

※ 12번 문제에 대한 답안은 교재에서 사용하는 pseudocode 형태로 알고리즘을 쓰시오.

 

 

(2) 과제 제출은 pdf 파일로 만들어서 Bb에 업로드한다.

---

Write a θ(n) algorithm that sorts n distinct integers, ranging in size between 1 and kn inclusive, where k is a constant positive integer. (Hint: Use a kn element array.)

k는 일정한 양의 정수이고, n개의 서로 다른 정수를 1에서 kn까지 정렬하는 θ(n) 알고리즘을 작성하라. (힌트: kn 요소 배열 사용)

 

https://ict-nroo.tistory.com/58

[Algorithm] 3-7. Counting Sort - 선형시간 알고리즘

Sort(A[],n)// n개의 배열을 갖는 배열 A
{
   int max=0;// n개의 수를 저장한다 max에
   for(int i=0;i<n;i++)// max 가 무엇인지 검사
   {
       if(A[i]>max)
       max = A[i];  
   }
  
   // max + 1 사이즈의 배열을 만든다.
   int f[max+1]={0};//모든 f의 값을 0으로 초기화
  
   for(int i=0;i<n;i++) //A의 수를 센다
   {
       f[A[i]]+=1;// 카운트 센다  
   }
  
   int k=0;
   for(int i=0;i<max;i++)//generating sorted sequence
   {
       if(f[i]!=0)
       {
           while(f[i]>0)
           {
               A[k]=i;//inserting in sorted order
               k++;
               f[i]=f[i]-1;  
           }  
       }
      
   }
  
   return A;//sorted list is returned
}

---

Algorithm A performs 10n^2 basic operations, and algorithm B performs 300 ln(n) basic operations. For what value of n does algorithm B start to show its better performance?

답 :

n= 7 일때 A = 40, B = 583.773

n= 8 일때 A = 640, B = 623.8325

따라서 n = 8 일 때 더 좋은 performance를 나타낸다.

---

Show directly that f(n) = n^2 + 3*n^3 ∈ Θ(n^3). That is, use the definitions of O and Ω to show that f(n) is both O(n^3) and Ω(n^3). 

 

답 :

Big O 의 정의 : 모든 0 < n0 ≤ n 에 대하여 0 ≤ f(n) ≤ c g(n) 인 양의 상수 c와 n0가 존재하면 f(n) = O(g(n)) 이다.

f(n) = n^2 + 3n^3 이며

n^2 ≤ n^3 이다.

 

n^2 + 3n^3 ≤ 4n^3 이고 n>1 일 때

n^2 + 3n^3 = O(n^3) 이다 (c=4, n0=1)

따라서 f(n) 의 Big O는 O(n^3)이다.

 

Ω 의 정의 : 모든 0 < n0 ≤ n 에 대하여 0 ≤ c g(n) ≤ f(n)  인 양의 상수 c와 n0가 존재하면 f(n) = Ω(g(n)) 이다.

f(n) = n^2 + 3n^3 이며

0 ≤ c n^2 ≤ 3n^3 이고

c가 1이고 n이 1일 때 위 식이 성립하므로

f(n) = Ω(n^3) 이다.

 

따라서 빅세타와 빅오메가가 참이므로 f(n) = θ(g(n)) 가 성립한다.

 

---

 

답 : (e)

답 : (c)

답 : (f)

---

Presently we can solve problem instances of size 30 in 1 minute using algorithm A, which is a Θ(2^n) algorithm. On the other hand, we will soon have to solve problem instnaces twice this large in 1 minute. Do you think it would help to buy faster (and more expensive) computer? 

현재 우리는 30사이즈의 문제 인스턴스를 ((2^n) 알고리즘인 알고리즘 A를 사용하여 1분 안에 해결할 수 있다. 한편, 우리는 곧 이만큼 큰 문제를 1 mi 단위로 두 배로 풀어야 할 것이다.

 

답 :

30개의 문제(n=30)를 Θ(2^n) 만큼으로 풀면 1개의 문재는 1/(2^30) 시간으로 풀 수 있다.

2배의 문제(n=60)를 풀려면 1개의 문제를 (1/2^60) 시간으로 풀 수 있으므로

2^30 = 1,073,741,824, 즉 10억배 빠른 컴퓨터를 사야한다. 

---

What is the time complexity T(n) of the nested loops below? For simplicity, you may assume that n is a power of 2. That is n = 2^k for some positive integer k.

 

답 :

바깥 루프(while (i>=1))는 값을 1부터 시작하여 1씩 증가시켜 1부터 n까지의 값에 대해 실행된다. -> n
안쪽 루프(while (j<=n))는 n에서 1까지의 값에 대해 매번 값을 절반으로 줄임으로써 실행된다. -> log(n)
따라서 T(n) = n*log(n) 이다.

 

 

---

시간 복잡도 & 공간 복잡도

 

모든 경우에 있어서 항상 우월한 성능을 보이는, 자료구조와 알고리즘은 없다.
그래서 자료구조와 알고리즘(이하 알고리즘)을 분석하고 평가할 수 있어야 한다.

알고리즘의 성능분석의 주된 요소는 두가지가 있다.

1) 공간 복잡도(Space Complexity) : 알고리즘에 사용되는 메모리 공간의 총량
2) 시간 복잡도(Time Complexity) : 알고리즘에 사용되는 연산횟수의 총량

즉, 공간복잡도는 메모리 사용량에 대한 분석결과이고 시간복잡도는 속도에 대한 분석결과이다.

1. 공간 복잡도

 위의 예에서 sum함수(sum이라는 알고리즘)의 공간복잡도는??
- n개의 배열요소를 가지는 list를 매개변수로 받을 경우 공간 복잡도는 n + 1이 된다.
  ( 배열요소 n개 + tempsum변수의 공간 1개 )
- n x m 배열을 받았을 경우 공간복잡도는  n*m + 1이 된다.

# 하지만 일반적으로 알고리즘을 평가할 때 메모리의 사용량보다 실행속도에 초점을 맞춘다.

2. 시간 복잡도

시간 복잡도의 경우 "연산의 횟수"를 센다.
어떤 함수를 돌렸을 때 결과를 반환할 때까지 걸리는 "실행시간"이 아니다.
만약 "실행시간"으로 시간복잡도를 계산할 경우 아래와 같은 단점이 있기 때문이다.

 1) 측정을 위한 완성된 프로그램이 필요하다.
 2) 모든 플랫폼(그냥 컴퓨터 or 슈퍼 컴퓨터)에서 동일한 결과를 산출하지 못한다.

 그렇기에 시간복잡도는 "연산의 횟수"이다. 즉, 시간복잡도의 단위는 시간이 아닌 시행횟수인 것.
연산횟수를 바탕으로 시간복잡도를 산출할 경우의 이점은

1) 실행이 필요하지 않다.( i.e. , coding)
2) h/w, s/w 가 필요하지 않다. - 수도코드로 충분히 계산간능하다.
3)모든 플랫폼에서 동일한 결과를 산출한다.

 위의 알고리즘의 시간복잡도는 ??
 - for문 내에서 10^6 회의 + i 의 연산을 거치므로 10^6이 된다.

3. 시간복잡도 구해보기

n을 input data의 개수로 정하고
T(n)을 data수에 대한 연산횟수를 구하는 함수로 지정해보자.

1) Linear Loops

좌측의 T(n)은 무엇일까?
n개의 data가 들어왔을 때 for문에서 n번 반복하므로
T(n) = n 


i+=2이므로
T(n)  = n/2

 이처럼 data n개에 대한 T(n)들이 n 혹은 n/2 일 경우 n에 대한 1차방정식이다.
n이 증가할 때 시간복잡도 역시 증가하되 선형적으로 증가한다.

2) Logarithmic Loops

 data n개에 대하여 i의 값은 1 2 4 8 16 ... 과 같이 제곱으로 
증가한다. 이는 비선형적으로 i가 증가하여 위의 예와 비교하여 
i가 n까지 도달하는 횟수가 더 적으며(for문의 종료조건)그만큼 연산의 횟수가 더 적음을 의미한다.
시간복잡도는 T(n) = log (n) (밑은 2) 이다.
 아래의 예 역시 동일하다.  

3) Nested Loops

T(n) = n^2 이다. 
입력데이터가 증가함에 따른 연산의 횟수 증가값이 아주 높다.
그래서 많은 데이터를 처리할 때 바람직하지 못한 알고리즘이다.
 알고리즘 문제를 풀때, 시간초과가 뜨는 경우 이런 유형의 시간복잡도를 가지는 함수가 있는지 확인해봐야 한다.

 

바깥 루프는 n 회 돈다.
안쪽 루프는 평균 (n+1) / 2 회 돈다.
(첫번째 시행에서 1번 두번째 시행에서 2번... 
 ..n번째 시행에서 n번 돌게되므로)
T(n) = n * (n+1) / 2

바깥루프는 n회 돈다.
안쪽루프는 평균 log (n) (밑2) 회 돈다.
T(n) = n * log(n)(밑2)