[JavaScript] 시간 복잡도

ubin·2023년 9월 3일

빅오표기법 시간복잡도 자바스크립트 코딩테스트

JavaScript

목록 보기

1/21

📍시간 복잡도란?

시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석하는 방법 (알고리즘이 얼마나 빠르게 수행되는가)

일반적으로 알고리즘 성능을 나타내는 척도 중 하나로, 보통 성능(performance)은 실행 시간(time)과 메모리(memory) 용량으로 평가된다.
알고리즘 같은 경우는 메모리를 적게 사용하면서 알고리즘의 수행 시간이 빠른 것이 좋은 알고리즘이라고 한다.
동일한 기능을 수행하는 알고리즘들이 있다면, 이들 사이에서 복잡도가 낮을수록 성능이 우수하다.
복잡도의 '복잡'이란 의미는 계산 복잡도에서 나온 단어로 좀 더 값이 크게 증가하는 정도를 의미한다. 즉 , 코드의 복잡성보다 수치적으로 값이 얼마나 더 큰지에 대해 초점을 맞춰야 한다.

📍빅오 표기법(Big-O Notation): 시간 복잡도 표기 방법

빅오 표기법: 복잡도를 판단하는 표기법 중에 하나로, 가장 빠르게 증가하는 항 하나만을 고려하여, 함수의 상한을 나타낸다.

복잡도는 어떠한 크기에 대한 의미를 가진다 = 수학적으로 수치를 나타낼 수 있어야 한다.
예시) 3N^3+5N^2+10000000 인 알고리즘이 있을 때, N이 증가함에 따라 첫 항인 3N^3을 제외한 다른 항의 영향력은 작아진다.
=> 빅오 표기법에서는 차수가 가장 큰 항에서 계수를 제외한 나머지를 O(N^3)으로 표현한다.

좋은 알고리즘 = 시간 복잡도가 낮을수록 좋음 (더 빠르거나, 메모리 적게 사용)
O(logN) 로그 시간이 좋은 쪽에 속해 있는 이유: 수학적인 관점을 보았을 때, log는 값을 굉장히 빠르게 줄여서 상수 시간에 가까울 정도로 빠르게 동작하기 때문이다.
예시) 밑이 2이고 지수가 N이라고 했을 때 N이 100만이면 log 100만 = 약 2^20 이므로 결과적으로 log 100만 => 20으로 줄일 수 있다.
O(1) 상수 시간 : 사칙연산을 수행하는 것
O(logN) 로그 시간 : 어떠한 알고리즘이 무언가를 절반씩 쪼갤 때 (이분 탐색)
O(N) 선형 시간 : 어떠한 배열이 있고, 하나씩 배열의 원소를 확인하면서 정해진 원소를 찾을 때
O(NlogN) 로그 선형 시간 : 정렬 알고리즘 (병합 정렬, 퀵 정렬 등..)
O(N^2) 이차 시간 : 동적 계획법
주어진 알고리즘에 따라서, 복잡도를 표기하여 알고리즘이 얼마나 빠르게 동작하는지 평가하고 수치적으로 표기하는 것

📍시간 복잡도 예시

** 수행 시간: 실질적으로 데이터의 개수가 N일 때 얼마만큼 반복이 수행되는지

(1) N 개의 데이터 합을 계산하는 프로그램

let array = [1,2,3,4,5]; //5 개의 데이터 (N=5)
let sum = 0; //합계를 저장할 변수

//모든 데이터를 하나씩 확인하며 합계를 계산 
for (let i = 0; i < array.length; i++) { 
	sum += array[i];
}

//결과 출력 
console.log(sum);

배열의 길이만큼 for 반복문으로 반복해서 더해주기 때문에 수행 시간은 배열의 길이이자 원소의 개수와 동일하다.
더하기 연산은 원소의 개수만큼 수행되므로, 수행 시간은 데이터의 개수 N에 비례할 것임을 예측할 수 있다.
더하기 연산은 N에 비례해서 증가하기 때문에 시간 복잡도는 N으로 O(N)으로 표기할 수 있다.

(2) N 개의 데이터 곱을 이중 반복문을 사용하여 계산하는 프로그램

let array = [1,2,3,4,5]; //5 개의 데이터 (N=5)

	for (let i = 0; i < array.length; i++) { 
		for(let j = 0; j < array.length; j++){
		let temp = array[i]*array[j];
		console.log(temp);
		}
	}

총 5개의 데이터가 있지만 i값이 1번 변할 때, j값은 5번 변하므로, 결과적으로 곱셈 연산이 5*5번 수행되는 것을 볼 수 있다.
곱셈 연산은 N^2에 비례해서 증가하기 때문에 시간 복잡도는 N^2으로 O(N^2)로 표기할 수 있다.
하지만 모든 이중 반복 문법의 시간 복잡도가 O(N^2)인 것은 아니다, 소스코드가 내부적으로 다른 함수를 호출할 수도 있기 때문에 잘 확인해야 한다.

📍알고리즘 설계 TIP

자바스크립트를 기준으로 1억 번의 연산 처리는 1~5초 가량의 시간이 소요된다.
문제에서 시간 제한이 명시되어 있지 않은 경우 대략 5초 정도로 염두해두고 푸는 것이 합리적이다.
예시) O(N^3)의 알고리즘을 설계한 경우, N의 값이 5000이 넘으면 얼마나 걸릴까?
- 대략 125억이므로 100초 이상이 걸린다고 할 수 있다.
- 이런 알고리즘은 N의 값이 5000이 넘을 땐 적합하지 않다는 것을 알 수 있다.