자료구조와 알고리즘(시간복잡도)

자료구조와 알고리즘은 컴퓨터 과학 분야에서 매우 중요한 개념입니다. 이들은 컴퓨터 프로그래밍에서 사용되는 툴이며, 이를 이해하고 응용하는 것은 컴퓨터 과학을 학습하는 사람들에게 필수적입니다. 이 글에서는 자료구조와 알고리즘에 대해 자세히 설명하고자 합니다.

자료구조란?

자료구조는 데이터를 구성하고, 저장하고, 조작하는 방법에 대한 규칙과 기술입니다. 프로그램이 실행되는 동안 데이터를 저장하고 조작하는 데 필요한 방법을 결정하는 데 사용됩니다. 자료구조는 크게 선형 자료구조와 비선형 자료구조로 나뉩니다.

선형 자료구조

선형 자료구조는 데이터를 일렬로 나열한 형태로 저장합니다. 이들은 단순하고 쉽게 구현할 수 있으며, 대표적인 예로 배열, 연결 리스트, 스택, 큐 등이 있습니다.

비선형 자료구조

비선형 자료구조는 데이터를 계층적인 구조로 저장합니다. 대표적인 예로 트리, 그래프 등이 있으며, 이들은 더 복잡하고 구현하기 어려울 수 있지만, 특정한 문제를 해결하는 데 매우 유용합니다.

알고리즘이란?

알고리즘은 주어진 문제를 해결하기 위한 일련의 절차와 규칙입니다. 컴퓨터 프로그램에서 알고리즘은 프로그램의 흐름을 결정하는 데 사용됩니다. 알고리즘은 계산, 데이터 처리, 자동화, 문제 해결 등 다양한 분야에서 사용됩니다.

자료구조와 알고리즘의 관계

자료구조와 알고리즘은 서로 긴밀하게 연결된 개념입니다. 효율적인 알고리즘을 설계하려면, 적절한 자료구조를 선택하는 것이 중요합니다. 예를 들어, 큰 데이터셋에서 특정 값을 검색하는 문제를 해결하려면, 배열보다는 이진 검색 트리나 해시 테이블과 같은 비선형 자료구조를 사용하는 것이 더욱 효율적일 수 있습니다.

또한, 자료구조와 알고리즘은 프로그래밍 언어나 컴퓨터 아키텍처에 따라 다르게 구현될 수 있습니다. 따라서, 특정한 알고리즘과 자료구조의 성능을 분석하려면, 이를 특정한 프로그래밍 환경에서 실행시켜야 합니다.

시간복잡도

시간 복잡도(Time Complexity)는 알고리즘의 실행 속도를 말한다

하나의 문제를 해결할때 다양한 알고리즘이 존재하고, 그중에 가장 빠르고 연산횟수가 적은 방법으로 코드를 작성하는것이 효율적이기 때문에 시간복잡도의 개념이 중요하다.

그 중 시간복잡도를 표현하는 빅오 표기법에 대해서 알아보겠습니다.

시간복잡도의 빅오 표기법이란

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)

(CS에선 log 아래 2가 생략되어있다.)

위의 순서대로 시간복잡도가 높아진다.

자바스크립트로 시간복잡도 표현

O(1)

for (let i = 0; i < 1; i+= 1){
	// ...
}

O(n)

for (let i = 0; i < n; i+= 1){
	// ...
}

O(log n)

for (let i = 0; i < n; i*= 2){
	// ...
}

O(n log n)

for (let i = 0; i < n; i+= 1){
	for (let i = 0; i < n; i*= 2){
	// ...
	}
}

O(n^2)

for (let i = 0; i < n; i+= 1){
	for (let i = 0; i < n; i+= 2){
	// ...
	}
}

빅오 표기법의 4가지 법칙

계수법칙, 합의법칙

계수 법칙

// 두 루프는 같은 O(n)으로 표기된다.
// 이유는 n 이 무한에 가까울수록 5의 크기는 의미가 없기 때문이다.
for(let i = 0; i < n; i += 1){
	// ...
}

for(let i = 0; i < n * 5; i += 1){
	// ...
}

합의 법칙

// 두 루프를 합쳐 O(n + m)으로 표기된다.
// 계수 법칙에 의해 5는 사라진다.
for(let i = 0; i < n; i += 1){
	// ...
}

for(let i = 0; i < m * 5; i += 1){
	// ...
}

곱의 법칙

// 두 루프를 곱해 O(n^2)으로 표기된다.
// 계수 법칙에 의해 5는 사라진다.
for(let i = 0; i < n; i += 1){
	for(let i = 0; i < n * 5; i += 1){
		// ...
	}
}

다항 법칙

// 다음 루프는 O(n^3)으로 표기할 수 있다.
for (let i = 0; i < n * n * n; i+= 1){
	// ...
}

정리

상수항은 무시

// 두 루프를 합쳐 O(n + m)으로 표기된다.
// 계수 법칙에 의해 계수는 사라진다.
for(let i = 0; i < n * 6; i += 1){
	// ...
}

for(let i = 0; i < m * 5; i += 1){
	// ...
}

가장 큰 항 외엔 무시

// 두 루프를 합하면 O(n^2 + n)이지만 작은항 무시하여
// O(n^2)으로만 표기해도 된다.
for(let i = 0; i < n; i += 1){
	// ...
}

for(let i = 0; i < n; i += 1){
	for(let i = 0; i < n; i += 1){
		// ...
	}
}

성능측정 방법

Date 객체를 이용

console.time('binary')
// ...
console.timeEnd('binary')