My Ability) 시간복잡도 / 효율적인 알고리즘으로 데이터를 다뤄보자!

백준우·2021년 11월 22일

시간복잡도 알고리즘

Ability

목록 보기

4/5

1. 시간복잡도란?

2. Big-O 표기법

3. 시간복잡도를 구하는 방법

1. 시간복잡도란?

우리는 어떤 일에대해 계획을 할때 시간적인 부분에서 최대한의 효율을 발휘해서 계획을 할것이다.
컴퓨터 프로그래밍에서도 시간복잡도가 가장낮은 알고리즘을 채택하는 것이 위와 같이 시간을 효율적으로 사용하는것이라고 할 수 있다.
예를들어 서울에서 대구까지 가는 과정을 알고리즘으로 표현 하자면 아래와 같을 것이다.

functoion 서울에서 대구까지(){
1. 집에서 서울역까지 버스를 타고 이동한다.
2. 가는길 가장가까운 시간대의 KTX을 예매한다.
3. 서울역에서 도착한뒤 기차를 탑승하고 대구로 출발한다.
4. 동대구역에서 하차한다. 
}

알고리즘이란?

어떠한 목적을 이루기위해 일련의 과정을 의미
다양한 방법이 존재하지만 시간복잡도가 다르므로 시간복잡도가 가장낮은 알고리즘을 선택하여 사용한다.

위와같이 효율적으로 알고리즘을 구현한다는것은 입력같이 증가함에따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 것입니다. 그리고 이를 나타내는 방법이 Big-O(빅오)표기법이라고 합니다.

점근적 표기법의 종류 (3가지)
1. 최상의 경우 : 오메가 표기법 (Big-Ω Notation)
2. 평균의 경우 : 세타 표기법 (Big-θ Notation)
3. 최악의 경우 : 빅오 표기법 (Big-O Notation)

2. Big-O 표기법

위 세가지 표현방법중 가장 많이 사용하는 것이 빅오 표기법입니다.
빅오 표기법은 최악의 상황을 고려하므로, 프로그램이 실행되는 과정에서 소용되는 최악의 시간까지 고려할 수있기 때문입니다. ("이정도 시간까지 걸릴 수 있겠다"를 고려해야 한다.)

왜 Big-O(빅오)표기법을 사용할까?

결과를 반환하는데 최선의 경우 1초, 평균적으로 1분, 최악의 경우 1시간이 걸리는 알고리즘을 구현했고, 최선의 경우를 고려한다고 가정할때 이 알고리즘을 100번 실행한다면 최선의 경우 100초가 걸린다. 하지만 최악의 경우 100시간이 걸리는 알고리즘이 되어 버린다. 평균값을 기대하는 시간 복잡도를 고려한다면 100분이 되어버린다. 때문에 최악의 경우가 발생하지 않도록 하기위해 다른 표기법 보다 빅오 표기법을 주로 사용했습니다.

Big-O 표기법 종류

O(1) : (constant complexity)
function O_1_algorithm(arr, index) {
	return arr[index];
}
let arr = [1, 2, 3, 4, 5];
let index = 1;
let result = O_1_algorithm(arr, index);
console.log(result); // 2
입력 자료의 수(n)에 관계없이 일정한 실행 시간을 갖는 알고리즘
EX) 배열에서 특정 인덱스 찾기, 해시테이블 추가

O(n) : (linear complexity)
function O_n_algorithm(n) {
	for (let i = 0; i < n; i++) {
	arr[i] = arr[i] + 1
	}
}
입력 자료의 수(n)에 따라 시간또한 같은 비율로 증가하는 알고리즘
EX) 연결 리스트 순회, 최대값찾기

O(log n) : (logarithmic complexity)

초반엔 빠르지만 후반부 갈수록 시간이 증가함, O(1)다음으로 빠른 시간복잡도를 가짐
EX) 이진 탐색(원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어듭니다.)

O(n^2) : (quadratic complexity)

입력값이 증가함에따라 시간이 n의 제곱수에 비율로 증가하는것을 의미
주로 2중 for loop를 사용하여 조합가능한 모든 쌍을 대상으로 하는 경우가 전형적(quadratic)
EX) 버블 정렬,삽입 정렬

O(2^n) : (exponential complexity)
function fibonacci(n) {
	if (n <= 1) {
		return 1;
	}
	return fibonacci(n - 1) + fibonacci(n - 2);
}
구현한 알고리즘의 시간 복잡도가 O(2n)이라면 다른 접근 방식을 고민해 보는 것이 좋습니다.
EX) 피보나치수열

3. 시간복잡도를 구하는 방법

각 문제의 유형을 파악하여 빠르게 알아볼 수 있다.

하나의 루프를 이용한 단일 요소 집합을 반복 => O (n)
데이터의 절반 이상을 반복 => O(n/2) -> O(n)
두개의 다른 루프를 사용하여 각기다른 값을 사용할 경우 => O (n + m) -> O (n)
두개의 중첩! 루프로 하나의 값을 반복하는경우 => O (n²)
두개의 중첩 루프문으로 두개의 다른 값을 반복하나는경우 => O (n * m) -> O (n²)
데이터 전체를 정렬하여 사용하는 경우 => O(n*log(n))

TIP 왜 O(4n) 이나 O(2n)이나 O(n)이 같은것일까?

2n, 5n 을 모두 O(n)이라고 표현하는 것처럼, n3과 n5 도 모두 O(n2)로 표기합니다.
n이 커지면 커질수록 지수가 주는 영향력이 점점 퇴색되기 때문에 이렇게 표기합니다.
같은 비율로 증가하고 있다면 2배가 아닌 5배, 10배로 증가하더라도 O(n)으로 표기합니다