time complexity (시간 복잡도)

참고 : 코드스테이츠 이머시브 강의

complexity analysis (복잡도분석)

: 알고리즘이 그것을 푸는데 있어서 시간과 공간을 얼마나 차지하는지 나타내는 지표

 

---

시간과 공간이 무한정으로 있다면?

알파고는 만들기 쉽다.

플레이 가능한 모든 가짓수를 계산하면 됨

 

그렇지만 시간과 공간이 어마어마하게 필요하겠지?

바둑판은 19x19 = 381가지 플레이

무한정의 경우의 수가 나올 수 있기 때문이다!!!

그렇기 때문에 시간복잡도를 고려해서

메모리를 적게 쓰는 코드를 쓰는 것이 중요하다는 것을 알고 포스팅을 시작해본다.

---

 

 

<연습문제> 시간과 배열이 주어졌다. 여기서 두 수의 가장 큰 차이를 구하라. 주어진 배열 : [2, 5, …, 16]

 

첫번째 방법

모든 숫자를 비교한다.

  2, 5, 6, ...

 

이렇게 계산했을 때 시간 복잡도는 O(n^2)

 

두번째 방법

그 배열안에서 가장 큰 수와 가장 작은 수를 찾기

 

이렇게 계산했을 때 시간 복잡도는 O(n)

 

세번째 방법

가정: 우리가 받은 배열이 이미 sort 된 배열이라면?

첫번째 원소와 마지막 원소만 알면 된다!

=> 마지막 원소 - 첫번째 원소

 

이렇게 계산했을 때 시간 복잡도는 O(1)

 

 

 

시간 복잡도의 종류

(출처 : https://velog.io/@junyong92/TIL-Time-Complexity)

상수 시간(Constant time), O(1)
어떤 알고리즘 T(n)이 입력의 개수나 크기에 구애받지 않는 값에 의해서 정해지는 경우 이 알고리즘의 시간복잡도는 O(1)이라고 한다.

예를 들어 배열에서 특정 인덱스의 값을 읽거나 링크드 리스트에 데이터를 삽입/제거 할 때

 

로그 시간(logarithmic time), O(logn)
T(n) = O(logn)인 경우 로그 시간이 걸린다고 한다. 어떤 알고리즘의 시간 복잡도가 로그 시간을 가질때, 높은 효율의 알고리즘이라고 할 수 있는데, 그 이유는 로그 함수처럼 입력의 크기에 따른 소요 시간의 증가율이 적기 때문이다.

이진 탐색 트리에서 특정 값을 찾는 경우를 예로 들 수 있다.

 

선형 시간(linear time), O(n)
시간 복잡도가 O(n)인 경우이며, 입력에 따라 걸리는 시간이 선형적으로 증가함을 의미한다.

일차원 배열이나 링크드 리스트에서 특정 값을 찾는 경우를 예로 들 수 있다.

 

선형 로그 시간(linearithmic time), O(n logn)

O(n^2)보다는 빠르지만, O(n)보다는 느리다. O(logn)의 시간이 걸리는 알고리즘의 n배의 시간이 걸린다고 할 수 있다. 이진 탐색 트리에서 노드의 삽입/제거는 O(logn)이 걸리는데, 데이터 삽입/제거 후 트리의 밸런스를 다시 잡는 자가 균형 이진 탐색 트리의 경우는 O(nlogn)이 걸린다.

 

다항 시간(quadratic time), O(n^2)
정수 n에 대한 선택 정렬 알고리즘이 상수 A에 대해서 An^2개의 연산을 수행한다. 그렇다면 이것은 O(n^2)의 시간동안 수행되며, 다항시간 알고리즘이라고 할 수 있다.

 

지수 시간(exponential time), O(2^n)
최악의 시간복잡도이다.

 

 

시간 복잡도의 효율성을 표로 나타낸 자료이다.

 

 

 

data structure with time complexity

 

1/ array

 

look up : O(1) index를 알고 있을 경우!

assign : O(1)

insert : O(n) 한칸씩 옮겨야하니까

remove : O(n) 지워진 칸에 다시 한칸씩 옮겨야한다.

find : O(n)

 

 

2/ singly linked list

 

look up : O(n)

assign : O(n)

insert : O(1)

remove :  head - O(1) / middle - O(n) (자신의 이전 노드를 모르기 때문에)

find : O(n)

 

 

3/ doubly linked list

 

look up : O(n)

assign : O(n)

insert : O(1)

remove :  O(1) (자신의 이전 노드를 안다!)

find : O(n)

 

 

4/ tree

 

value와 children이라는 참조를 가짐

 

find: O(n)

 

 

5/ BST (Binary Search Tree)

 

조건이 있음

왼쪽 자식이 더 작고 오른쪽이 자식이 더 크다는 조건.

 

find: O(log n)

 

 

한 눈에 보기 쉽게 표로 정리해보자.

	array	singly linked list	doubly linked list	tree	BST
look up	O(1)	O(n)	O(n)
assign (재정의)	O(1)	O(n)	O(n)
insert (추가)	O(n)	O(1)	O(1)
remove (제거)	O(n)	O(1) / O(n)	O(1)
find (찾기)	O(n)	O(n)	O(n)	O(1)	O(log n)

 

---

결론은 각 데이터 구조의 장단점을 알아야

어떤 코드를 구현할 때 어떤게 더 효율적일지 알 수 있다.

왜냐면 데이터의 양에 따라 효율적인 구조가 다르기 때문이다.

 

 

그리고 시간복잡도 cheat sheet은 https://www.bigocheatsheet.com/ 여기 참고