알고리즘 복잡도 표현 방법 : 시간 복잡도

알고리즘 복잡도 표현 방법

 

1. 알고리즘 복잡도 계산이 필요한 이유

하나의 문제를 푸는 알고리즘은 다양할 수 있음

ex) 정수의 절대값 구하기

- 방법1 : 정수값을 제곱한 값에 다시 루트를 씌우기

- 방법2 : 정수가 음수인지 확인해서, 음수일 때만 -1을 곱하기

다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산함

 

2. 알고리즘 복잡도 계산 항목

• 시간 복잡도 : 알고리즘 실행 속도
• 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈

가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 함

 

알고리즘 시간 복잡도의 주요 요소

반복문으로 계산

 

3. 알고리즘 성능 표기법

• Big O (빅-오) 표기법 : O(N)
  • 알고리즘 최악의 실행 시간을 표기
  • 가장 많이/일반적으로 사용함
  • 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 떄문
• 오메가 표기법 : 오메가(N)
  • 오메가 표기법은 알고리즘 최상의 실행 시간을 표기
• 세타 표기법 : 세타(N)
  • 오메가 표기법은 알고리즘 평균 실행 시간을 표기

 

대문자 O 표기법

• 빅 오 표기법, Big-O 표기법 이라고도 부름
• O(입력)
  • 입력 n에 따라 결정되는 시간 복잡도 함수
  • O(1), O(logn), O(n), O(nlogn), O(n^2), O(2^n), O(n!) 등으로 표기함
  • 입력 n의 크기에 따라 기하급수적으로 시간 복잡도는 늘어날 수 있음
  • O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)
• 단순하게 입력 n에 따라 몇번 실행이 되는지를 계산하면 됨
  • 표현식에 가장 큰 영향을 미치는 n의 단위로 표기한다.
  • 상수회 : O(1)
  • n + 10 3n + 10 등 : O(n)
  • n^2 100n^2 + 100 등 : O(n^2)
• ex) 만약 시간 복잡도 함수가 2n^2 + 3n -> 빅 오 표기법으로는 O(n^2)

 

4. 실제 알고리즘을 예로 각 알고리즘의 시간 복잡도와 빅 오 표기법 알아보기

• 1부터 n까지의 합을 구하는 알고리즘1 
  • 시간 복잡도 : n 빅 오 표기법으로는 O(n)

public Integer sumAll(Integer n) {
	Integer total = 0;
    for (num = 1; num < n + 1; num++) {
    	total += num;
    }
    return total;
}

• 1부터 n까지의 합을 구하는 알고리즘2
  • 시간 복잡도 : 1 빅 오 표기법으로는 O(1)

public Integer sumAll(Integer n) {
	return int(n * (n + 1) / 2)
}