[Algorithm] 시간 복잡도와 빅 오 (Big-O Notation)

 

시간 복잡도

주어진 문제 해결을 위한 연산의 횟수를 말한다.

일반적으로 1억번의 연산을 1초의 시간으로 간주해 예측함.

 

시간 복잡도 유형
빅 - 오메가 (Ω(N))	최선의 연산 횟수를 나타냄
빅 - 세타 (Θ(N))	보통의 연산 횟수를 나타냄
빅 - 오 (O(N))	최악의 연산 횟수를 나타냄

 

알고리즘에서 빅 - 오 표기법 (O(N)) 을 기준으로 시간을 계산해야한다.

즉, 가장 최악을 염두해 두고 문제를 풀어 나가야한다는 것!

(출처) Do it 알고리즘

 

 

시간 복잡도 도출하기

 

1. 상수는 계산에서 제외

ex ) 2N + 1  → O(N) , 6N²  →  O(N²)

상수는 시간계산에 크게 영향을 끼치지 않는다. 

 

2. 식의 값을 가장 큰 대표항만 남겨서 나타낸다.

 ex ) N² + N→ O(N²)

 

 

 

 

예시 1. ) N 이하의 자연수 중 3의 배수이거나 5의 배수인 수를 모두 합한 값을 반환하는 로직

 

3 ~ N 까지 반복문 수행 → N 번 반복 → O(N) 의 복잡도를 가짐.

 

 

예시 2.) 배열에서 가장 작은 수를 제거하는 로직

만약 arr[0] 제일 작은 수가 아니라면 

반복문을 arr.length 만큼 2번 반복함 → 2N 번 반복 →  상수(2) 제외 →  O(N) 의 복잡도를 가짐.

 

 

예제 3) int[] arr에 값을 넣는 로직

N번까지 반복하는 반복문2개를 중첩  → N² 반복 → O(N²) 의 시간 복잡도를 가짐

 

만약 아래에 일반 반복문이 더 있다 해도 가장 큰 복잡도로 유지. 

 

 

시간 복잡도를 계산해 효율적인 코드를 작성하자!