자료구조와 알고리즘, 복잡도 분석

프로그램은 큰 틀에서 보았을  때 자료구조+알고리즘 의 형태이다.

 

자료구조란?

프로그램에서 사용되는 자료를 표현하고, 저장, 조작하는 방법 및 수단을 말한다.

대표적으로 스택, 큐, 리스트, 트리 등이 있다.

 

알고리즘이란?

컴퓨터로 문제를 해결하기 위한 단계적 절차를 기술하는것을 말한다.

 

알고리즘의 성능을 분석하고 알고리즘의 효율성을 높여서 프로그램을 최적화하고 빠르게 작동할 수 있도록 한다.

알고리즘의 성능을 분석하기 위한 두 가지 방법을 보자.

 

1. 수행시간을 측정하는 방법

두 개의 알고리즘을 실행하고 실제 실행시간을 측정하고 비교하여 더 효율적인 알고리즘을 선택하는 방법이다.

하지만 두 개의 알고리즘을 실제 프로그램으로 구현해야하고 동일한 하드웨어,

사용된 언어 등 동일한 조건을 갖춰야 확실하게 비교가 된다.

 

2. 알고리즘 복잡도 분석

알고리즘이 수행하는 연산횟수를 측정하고 비교하는 방법이다.

이 방법은 알고리즘을 실제로 구현해야 할 필요가 없고 위의 방법처럼 동일한 조건을 갖춰야 할 필요가 없다.

복잡도 분석에도 두 가지가 있다.

시간 복잡도 분석 - 알고리즘에 포함된 연산횟수를 분석한다. (배정, 비교, 이동 연산 등)

공간 복잡도 분석 - 알고리즘이 필요로 하는 메모리 공간을 분석한다.

 

 

위의 두 가지 방법 중 성능 분석을 위해 알고리즘 복잡도 분석을 주로 사용한다.

복잡도는 입력 크기에 대한 다항식 형태의 함수로 표기하는데,

다항식을 단순한 함수로 표기하기 위하여(ex. 입력의 크기가 무한대로 커질 때, 복잡도를 간단하게 표현)

점근적 표기(asymptotic notation)를 사용한다.

점근적 표기법에는 세 가지 예가 있다.

 

1. O(Big-O)표기, 빅오 표기법 ( 점근적 상한 표기 )

2. Ω(Big-Omega)표기, 빅오메가 표기법 ( 점근적 하한 표기 )

3. θ(Theta)표기, 세타 표기법 ( 점근적 상한, 하한 동시 적용 )

 

 

그 중 가장 많이 사용되는 O(Big-O)

 

1. O(Big-O)표기법

두 개의 함수 f(n)과 g(n) (다항식의 최고차항)이 주어졌을 때, 모든 n ≥ n₀ 에 대하여

│f(n)│≤│g(n)│ 을 만족하는 2개의 상수 C 와 n₀ 가 존재하면 f(n) = O(g(n)) 이다.

 

ex. f(n) = 5 ➞ O(1)

      f(n) = 2n + 1 ➞ O(n)

      f(n) = 3n² + 100 ➞ O(n²)

      f(n) = 5 X 2ⁿ + 10n² + 1000 ➞ O(2ⁿ)

 

빅오 표기법의 종류

O(c) 또는 O(1) : 상수형, 상수 시간 알고리즘 (constant time algorithm)
 - 입력 크기(개수)에 관계없이, 항상 일정한 수행 속도(계산 횟수)
 - 가장 효율적임을 뜻함
 - 例) 배열에 있는 항목을 인덱스를 사용하여 접근할 때, 집합 내 요소로의 접근 등


O(log n) : 로그형, 로그 시간 알고리즘 (logarithmic time algorithm)
 - 로그 함수 형태 알고리즘 (밑이 2인 로그함수 : log₂ )
  . 통상, 데이터가 2배로 증가할 때, 연산수가 1 단계 씩 늘어나는 형태
 - 입력 개수가 증가하면서 포물선 곡선이 한쪽으로 수렴하므로, 
  . 데이터가 많아질수록 우수 수행 성능
 - 例) 이진 검색 등


O(n) : 선형, 선형 시간(1차 시간) 알고리즘 (linear time algorithm)
 - 선형 함수 형태 알고리즘
  . 입력 개수에 단순 비례적으로 수행 시간이 길어짐
 - 최악의 경우에 입력 개수 만큼 연산을 수행해야 함
 - 例) 중첩되지 않은 통상의 반복문, 선형 검색, 자연수의 거듭제곱 등


O(n log n) : 선형로그형, n 로그 시간 알고리즘 (n log n time algorithm)
 - 例) 반복문 증가 스텝이 2의 배수로 하여 2,4,8,16,32,64 처럼 증가하는 경우, 병합정렬 등


O(n²) : 2차형, 평방 시간(2차 시간) 알고리즘 (quadratic time algorithm)
 - 문제 해결 단계의 수가 입력값 n의 제곱으로 증가
  . n이 적을 경우에 만 사용해야 하는 느리고 비효율적인 알고리즘
 - 例) 2번 중첩된 반복문(이중 루프 for 문), 버블정렬,삽입정렬,선택정렬 등


O(n³) : 3차형, 3차 시간 알고리즘
 - 例) 3번 중첩된 반복문(for 문) 등


O(n^k) : 다항식 시간 알고리즘 (polynomial time algorithm)
 - 입력 크기에 대한 다항식으로 나타나는 알고리즘
  . 다항식 : 입력 n과, n^k(n의 상수 거듭제곱)들의 선형 결합으로 이루어진 식
  . 즉, O(n),O(n²),O(n³), ... O(n^k) 모두를 가리킴
 - 주로, 중첩된 반복문의 수행 횟수를, 입력 크기의 다항식으로 표현할 수 있는 알고리즘들
  * 한편,
   . 다항 시간 내 풀 수 있으면, 다루기 쉬운(tractable), P 문제 라고 하고,
   . 다항 시간 내 풀 수 없으면, 다루기 힘든(intractable), NP 문제 라고 함


O(2ⁿ) 또는 O(rⁿ) : 지수형, 지수 시간 알고리즘 (exponential time algorithm)
 - n이 하나 증가할 때 마다, 걸리는 시간이 그전보다 2배 또는 r배로 걸리는 매우 나쁜 사례 


O(n!) : 팩토리얼형, 계승 시간 (factorial time algorithm)
 - 지수 시간 보다 더 많이 걸림 (더 빠르게 증가함)
 - 따라서, 초 지수 시간(super-exponential)이라고도 함
 
 
O(∞) : 종료되지 않는 무한 루프


※ 시간복잡도 연산 크기 순서
 - O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(∞)



※출처 : http://www.ktword.co.kr/test/view/view.php?m_temp1=6146

 

2. Ω(Big-Omega)표기법

모든 n ≥ n₀ 에 대하여│f(n)│≥ C│g(n)│ 을 만족하는 2개의 상수 C 와 n₀ 가 존재하면 f(n) = Ω(g(n)) 이다.

 

3. θ(Theta)표기법

모든 n ≥ n₀ 에 대하여 C₁│g(n)│≤ │f(n)│≤ C₂│g(n)│ 을 만족하는 3개의 상수 C₁ , C₂ 와 n₀ 가 존재하면 f(n) = θ(g(n)) 이다.

* f(n) = O(g(n)), f(n) = Ω(g(n)) 이면 f(n) = θ(g(n)) 이다.

 

 

동일한 알고리즘이 입력값에 따라서 다른 수행 결과를 가질 때, 알고리즘을 3가지 경우로 평가한다.

 

1. 최악의 경우 ( worst case )

2. 최선의 경우 ( best case )

3. 평균의 경우 ( average case )

 

대부분 최악의 경우를 판단하고 최악의 경우를 제외하는 방식으로 알고리즘의 효율을 높인다.