자료구조의 기본(시간 복잡도, 빅오 표기법, 공간 복잡도)

[jcrescent61]

자료구조의 기본

자료 구조(Data structure)란 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장 할 수 있는 데이터 집합을 뜻한다.

 

시간 복잡도

시간 복잡도(Time complexity)는 알고리즘이 실행되는데 걸리는 시간을 뜻하며. 알고리즘에 의해서 수행되는 기본 연산의 개수를 세어 예측할 수 있다. 주로 빅오 표기법(Big-O)으로 나타낸다.

 

시간 복잡도로 측정해야하는 이유

시간복잡도 즉, 로직이 몇 번 반복 되었는가를 세어 측정하는 이유는 컴퓨터 성능이나 각자의 상황이 다르므로 같은 로직이라 하더라도 실행되는 시간이 상이하기 때문이다. 실제로 같은 컴퓨터로 실행한 경우에도 실행할때마다 처리 시간이 다르다.

console.time("test")

let sum = 0;
    
for(let i = 0; i < 10000000; i++) {
    sum += 1;
}

console.timeEnd("test")

 

시간복잡도가 필요한 이유

효율적인 코드 작성을 위한 기준이 될 수 있기 때문이다. 어떠한 로직을 효율적으로 바꿨다는 지표를 단순히 'O(𝚗²)에서 O(㏒ 𝚗)으로 개선했다.' 라는 형식으로 표현하면 간결하기 때문이다.

 

빅오 표기법(Big-O notation)

빅오 표기법이란 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론, 해석학의 방법이다. 복잡도에 가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항을 없애서 복잡도를 나타내는 표기법이다.

 

가장 많이 영향을 끼치는 항이란?

입력 크기가 커질수록 증가 속도가 커지는 항을 뜻한다.

어떤 로직이 10𝚗²+𝚗 인 경우 영향을 가장 많이 끼치는 항인 10𝚗²이 남고 상수 인자를 빼면 𝚗²이 남는다.
결국 O(𝚗²)이 된다.

Big-O Complexity Chart

이미지 출처: Big O Cheat Sheet – Time Complexity Chart

 

공간 복잡도

공간 복잡도(Space complexity)는
입력 크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양을 뜻한다. 알고리즘이 완전히 실행될 때까지 필요한 메모리이다. 정적변수로 선언된 . 것말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요한 경우도 포함되며 배열, 맵, 셋 등등 요소들을 담은 공간들은 모두 다 적용된다.

 

공간 복잡도 예시

인풋이 𝚗이 들어왔고 그에 따라 𝚗개 짜리 int형 요소를 담아야 할공간이 필요하면 4𝚗바이트의 공간이 필요하다. Big-O 표기법으로 나타내면 O(𝚗)이 된다.
하지만 공간 복잡도는 문제를 푸는데에 잘 사용되지는 않는다고 한다.

 

문제를 풀때 배열의 범위 등을 잡는 방법 2가지

1. 최대 범위

문제의 최대범위를 기반으로 배열을 미리 만들곤한다.

 

2. 메모리 제한

메모리 제한에 따라 문제를 푸는데 좋은 지표가 된다. (나중에 코테 풀때 경험해 볼 수 있다.)