알고리즘 평가기준 - 시간복잡도와 점근표기법-O(n)

이 글은 코드잇의 알고리즘 강의와 오픈소스들을 참고하여 정리한 글입니다^^

알고리즘 평가의 2가지 기준

1. 시간 : 빨리빨리 => 더 중요
2. (메모리)공간 => 돈 주고 사면 됨

시간 복잡도(Time Complexity)

컴퓨터 과학에서 알고리즘의 시간평가 방법

• 걸리는 시간으로는 판단x
  
  

• 데이터(리스트의 원소 개수)가 많아질수록 걸리는시간이 얼마나 급격히 증가하는지
  예를 들어, 리스트의 원소 개수가 10개, 20개, 100개 -> 걸리는 시간 10, 20, 100초라면 -> 걸리는 시간 일정하게 증가
  

  그러나 알고리즘 B는 걸리는 시간 증가량이 급격하다
  

  A보다 B의 시간복잡도가 크다.! = A 알고리즘이 시간 복잡도가 더 작은 빠른 알고리즘
  

시간복잡도 계산을 위한 거듭제곱과 로그

거듭제곱 (Exponentiation)

• 패턴을 따라가다보면 2의 -1승은 2의 0승(1) / 2 이므로 1/2 임을 알 수 있다.
  
  

로그 (Logarithms)

• a는 밑수 b는 진수 라 부른다.

• 편하게 생각하기 위해서는 a를 몇번(x) 곱해야 b가 나오는지로 생각한다.
  

• 혹은 b를 a로 몇번 나누어야지 1이 되는가? 이다.

• 컴퓨터 알고리즘 문제에서는 a가 2인 경우가 많다.

• log2(16)은 16을 2로 몇번 나누어야(몇번 반토막내야) 1이 나오는지 생각해보면, 4번이다.

• 예를 들어, 길이가 16인 리스트가 있다면, 총 4번 반토막 내어야한다.
  그림으로 예를 들면,
  

  이 상태에서 총 4번을 반토막 내야 1이 된다.
  
  
  
  

  log2( ) 를 lg로 쓰기도 한다.
  

시간복잡도 계산을 위한 1부터 n까지의 합

1부터 n까지의 합을 나열하여 T라 나타내고, 밑줄에 반대로 나열해놓고 더하자

2T = n * (n+1)
T= n(n+1) /2

점근 표기법 (Big-O Notation)

알고리즘은 일반적으로 걸리는시간(X) 인풋에 따라 걸리는 시간의 증가량에 의해 평가된다고 하였다.

하나의 알고리즘은 인풋에 따라 걸리는 시간이 달라진다.
즉, 알고리즘 소요시간 = 인풋크기(n)의 수식으로 나타낼 수 있다.

예를 들어, 아래 리스트를 인풋한다고 가정했을 때 리스트의 길이(n)라면,
알고리즘 소요시간 = 20n+40 or 2n^2 + 8n +157 일수도 있다.

그러나 n에 붙은 숫자들은 컴퓨터의 환경적인 것들에 의해 달라진다.

즉, 수식하나가지고는 하나의 알고리즘을 완벽하게 나타내지는 못한다.

그래서 컴퓨터 과학자들이 다같이 약속한 것이 점근표기법으로 알고리즘을 평가하자는 것이다.

점근표기법의 룰

1. 만약, 소요시간이 20n+40이라면?

   • n의 영향력이 작은 40 삭제(영향력 젤 큰 항만 남김) -> n앞에 계수 삭제 -> n만남아서 O(n)으로 표기
   • 해당 알고리즘을 Big-O of n 알고리즘이라 부른다.
     

2. 소요시간이 2차식이라면?

   • 가장 영향력이 큰 2n^2 만 남김 -> 앞에 계수 삭제 -> O(n^2)
   • Big O of n^2 알고리즘
     

3. 20lg(n) + 60 ?

   • 60 없앰 -> 20없앰 -> O(lg(n))
   • Big O of lg(n) 알고리즘
     

점근표기법을 위와 같이 표기하는 이유?

점근 표기법의 핵심 : n이 엄청 크다고 가정 -> my)낮은차수와 계수는 무시된다.
절대적인 시간보다는 성장성을 보기위함이다.

• n(input, 리스트의 길이, 원소의 개수)가 얼마 안되면, 굳이 좋은 알고리즘을 쓸 필요가 없다.
  
• 골치 아픈 경우는, n이 엄청 컸을 때의 알고리즘이다.

만약, 한 알고리즘의 소요시간이 n(리스트의 길이)에 대한 수식으로 2n^2 + 8n + 157로 나타났다고 가정하자.
그리고 2n^2 과 점근표기법에서 삭제되는 8n+157을 n에 대한 소요시간 그래프로 나타내보자.

• 처음에는 8n+157의 소요시간이 더 크더라도, 나중에는 2n^2의 소요시간이 압도적으로 커진다.
  

• n이 100만 정도로 엄청 커졌을 때, 차이는 두드러진다. 즉, n이 엄청 크다고 가정하면 영향력이 작은 부분은 그냥 무시해버리는 것이 핵심이다.
  

• 2n^2이 아니라 0.01n^2이라면??? -> 결과적으로 계수도 무시해도 된다
  

점근표기법의 의미

O(1) : Big-O of 1 알고리즘은 인풋사이즈(n)에 영향받지 않고 일정하게 1초가 걸린다.

O(n) : 인풋(n) 증가량(n배)과 소요시간이 비례(n배)해서 증가한다.

• 리스트 크기가 100 -> 1초, 200 -> 2초...
  

O(n^2) : 인풋(n) 2배 -> 소요시간(n^2) 4배 증가
O(n^3) : 인풋이 n배 -> 소요시간 n^3배 증가

n이 1000까지라면,,,

n이 10000까지라면,,, 더 차이가 난다.

• O(n^3)은 너무 오래걸리니 안좋은 알고리즘이다.
  

같은 컴퓨터가 아니라... 오래걸리는 알고리즘에 최고사양 컴퓨터를 배정한다면? 소요시간이 더 줄 수 있다.

그러나, 이것은 리스트의 길이가 적을 때의 이야기이다.
BigO의 핵심은 n이 무수히 크다고 가정하는 것이고,
그 상태에서는 리스트의 길이(n)이 증가함에 따라 소요시간(n) 폭팔적으로 증가하여, 결국은 n의 차수가 높은 O(n^3)이 가장 오래 걸릴 것이다.

즉, 컴퓨터 사양이 아무리 좋아도, 빠른 언어를 사용하여도,
결국 알고리즘이 별로면, 싸구려 컴퓨터보다 느려진다.