시간복잡도

1Hoit·2023년 8월 17일

코딩테스트

목록 보기

2/3

시작하며

이번 포스팅에서는 시간 복잡도에 대해 다뤄보고자 한다!
다만 깊이있게 들어가지 않고 문제를 풀 때 어떻게 생각하고 대처해야하는지 정도만 알아볼 예정이다.

시간복잡도

시간 복잡도는 알고리즘의 성능을 나타내는 척도이다.
즉, 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석을 분석하는 것이다.
동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 우수하다
다양한 표기법 중 빅오 표기법을 알아보자

빅오 표기법(Big-O Notation)

가장 빠르게 증가하는 항만을 고려하는 표기법으로
함수의 상한(가장 빠르게 증가하는 것)만을 나타내게 된다.
예시) 연산 횟수가 $3𝑁^3 + 5𝑁^2 + 1,000,000$ 인 알고리즘이 있다면 ?

• 𝑁이 증가함에 따라서, $3𝑁^3$ 을 제외한 다른 항의 영향력은 작아진다.
• Big-O 표기법에서는 차수가 가장 큰 항에서 계수를 제외하여 $𝑂(𝑁^3)$ 으로 표현된다.

시간 복잡도 예시 1)

𝑁개의 데이터의 합을 계산하는 프로그램 예제

let array = [3, 5, 1, 2, 4]; // 5개의 데이터(N = 5)
let summary = 0; // 합계를 저장할 변수
// 모든 데이터를 하나씩 확인하며 합계를 계산
for (let i = 0; i < array.length; i++) {
summary += array[i];
}

console.log(summary);

수행 시간은 데이터의 개수 𝑁에 비례함을 예측할 수 있다.

시간 복잡도: $𝑂(N)$

시간 복잡도 예시 2)

2중 반복 문법을 이용하는 프로그램 예제

let array = [3, 5, 1, 2, 4]; // 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);
		}
	}