[Datastructrue] Time Complexity

시간 복잡도는 알고리즘을 실행하는 데 걸리는 시간을 설명하는 계산 복잡도입니다.

시간복잡도는 일반적으로 알고리즘에 의해 수행되는 기본 연산의 수를 계산하여 추정되며, 각 기본 연산은 고정 시간이 걸린다고 가정합니다.

- wikipedia -

어떤 문제에 대한 알고리즘이 다 같을수는 없을것이다. 시간복잡도는 그러한 알고리즘을 컴퓨터가 실행했을때 얼마만큼의 시간에 대한 퍼포먼스를 보여주는지 측정해주는 지표같은것이다.

예를 들면, 

어떤 한 숫자가 요소인 배열이 있고 그 배열에서 두 숫자의 차의 최대값을 구하는 문제를 풀어본다면, 많은 알고리즘들이 나올수 있다.

let arr = [3,6,5,7,9];

1. 각각의 원소마다 비교를 하면서 차의 최대값을 구한다.

==> 일일이 원소를 체크하면서 모든 원소에 대한 차이를 구한다. 

2. 가장 큰 값과 가장 작은값을 구해서 차의 최대값을 구한다.

==> 배열순회를 2번 진행해서 최소와 최대를 구한다.

3. 정렬한 후, 제일 앞의 값과 제일 뒤의 값의 차를 구한다.

==> 이미 정렬이 되있으므로 배열의 제일 앞과 뒤의 값으로 구한다.

굳이 컴퓨터가 아니더라도 3번이 가장 빠른 방식인걸 알수가 있다.  시간복잡도는 이러한 알고리즘을 Big O notation이라는 표기법으로 표현을 하게 된다.

위키에 나와있는데로 기본연산의 수를 계산해서 구해주면 된다.

1번 알고리즘을 적용한다면 

let arr = [3,6,5,7,9];

// 3 -> 6,5,7,9
// 6 -> 5,7,9
// 5 -> 7,9
// 7 -> 9

// 4+3+2+1 번 연산한다.

// 원소가 n개 라면?
// 1+2+3+...+n-1 번 연산하게 된다.

big o 표기법으로 표기하면 o(n^2)이 된다. ( xn^2 + yn ... 이렇게 나오지만 최고차항만 써주면 된다.)

2번을 적용한다면

let arr = [3,6,5,7,9];

// 최소값은 배열전체를 1번 순회해서 구한다.
// 최대값은 배열전체를 1번 순회해서 구한다.

big o 표기법으로 표기하면 o(n)이 된다. (n번 + n번 = 2n 이지만 앞의 계수는 생략한다.)

3번은 

let arr = [3,6,5,7,9];
arr.sort(); // 정렬이 이미 되있다고 가정

// arr[0], arr[4]만 뽑아서 계산해주면된다.

big o 표기법으로 표기하면 o(1)이 된다.

(여기서 연산은 arr[0], arr[4] 그리고 그 둘의 차를 구하는것 , 3번 밖에 일어나지 않는다. 이것은 n이 커져도 고정이다.)

위 그래프를 보면 가장 빠른것은 3번이다.

프로그램의 효율성이나 성능 이런것을 봤을 때 어떤식으로 코드를 짜야하는지 알수가 있다. 그래서 시간복잡도라는 개념이 중요한것이다.