1 알고리즘 분석 ¹

알고리즘 특성

1. 입력(Input) - 없거나 그 이상
2. 출력(Output) - 최소 1개 이상
3. 명확함(Definiteness) - 변하지 않는 명확한 작업단계를 가져야 함. \(\sqrt{-1}\)
4. 유한성(Finiteness)
5. 유효성(Effectiveness): 구현할 수 있고 실용적이어야 함.

2 알고리즘 작성

알고리즘 swap(a,b)
{
  temp = a;
  a = b;
  b = temp;
}

swap <- function(a,b) {
  
  temp  <- a
  a     <-  b
  b     <-  temp
  result <- c(a, b)
  return(result)
}

swap(1,2)

[1] 2 1

알고리즘 성능평가

1. 시간 (Time) : 얼마나 빠른가?
2. 공간 (Space) : 얼마나 메모리를 적게 사용하는가?
3. 네트워크 부하: 클라우드 시대 강조됨.
4. 전력(Power) 사용량
5. CPU 레지스터

상기 알고리즘(swap)에 대해서 시간 복잡도와 공간 복잡도는 다음과 같다.

• \(f(n) = 4\) : 4단계
• \(S(n) = 4\) : a, b, temp, result

사실, 이런 단순한 경우 알고리즘 성능평가가 무의미하지만, 지금에서 화성에 가는 알고리즘을 제작할 경우 시간 복잡도와 공간복잡도 뿐만 아니라 다양한 요인을 고려해야된다. 이유는 어떤 알고리즘을 취하냐에 따라 결과가 극도로 달라지기 때문이다.

A <- c(8,3,9,7,2)

calculate_sum <- function(A, n) {
  sum_val <- 0
  for(i in 1:n) {
    sum_val <- sum_val + A[i]
  }
  return(sum_val)
}

calculate_sum(A, 1)

[1] 8

calculate_sum(A, 2)

[1] 11

calculate_sum(A, 5)

[1] 29

Frequency Count Method을 적용하여 상기 calculate_sum() 함수를 분석하면 다음과 같다.

• 시간 복잡성: \(f(n) = 2n + 3\)
  • for 루프 \(n+1\), sum_val \(n\), 반환 1 = \(2n+3 \approx O(n)\)
• 공간 복잡성: \(S(n) = n + 3\)
  • A - n, n - 1, sum_val - 1, i = 1 = \(n + 3 \approx O(n)\)

A <- diag(x = 1, nrow=3, ncol=3)
B <- matrix(1:9, nrow=3)

matrix_sum <- function(A, B, n) {
  sum_mat <- matrix(1:(n*n), nrow=n)
  
  for(i in 1:n) {
    for(j in 1:n) {
      sum_mat[i,j] <- A[i,j] + B[i,j]
    }
  }
  return(sum_mat)
}

matrix_sum(A,B,1)

     [,1]
[1,]    2

matrix_sum(A,B,2)

     [,1] [,2]
[1,]    2    4
[2,]    2    6

matrix_sum(A,B,3)

     [,1] [,2] [,3]
[1,]    2    4    7
[2,]    2    6    8
[3,]    3    6   10

Frequency Count Method을 적용하여 상기 행렬 합을 구하는 matrix_sum() 함수를 분석하면 다음과 같다.

• 시간 복잡성: \(f(n) = 2n^2 + 2n +1 \approx O(n^2)\)
  • for(i in 1:n) → \(n+1\)
  • for(j in 1:n) → \(n \times (n+1)\)
  • sum_mat[i,j] <- A[i,j] + B[i,j] → \(n \times n\)
• 공간 복잡성: \(S(n) = 3n^2 + 3\)
  • A, B, sum_mat → \(n^2\)
  • n, i, j → \(3\)