time complexity

 

 

Complexity Analasis 복잡도 분석

문제를 해결할 때 필요한 시간과 공간(저장공간)을 계산한 것을 말한다.

 

복잡도 분석을 하는 이유는? 

   알고리즘의 효율성을 위해서!

 

문제가 작을 때에는 알고리즘에 대한 효율성은 문제가 되지 않지만 문제가 커질수록 복잡도 분석이 중요해진다.

 

시간 복잡도를 표현하는 방식으로는 Big O 표기법을 사용한다.

en.wikipedia.org/wiki/Big_O_notation

Big O notation - Wikipedia

 

어렵다,,무슨말인지 허허 그렇다면!!!

문제를 보면서 이해해보자!

 

Q. 배열 안의 정렬된 n개의 수가 있을 때 두 수의 차가 가장 큰 것을 고르기.

 

1안. 두 수의 차를 모두 생각해보는 방법 

  => 시간 복잡도는 n * n = O(n^2)

배열 안의 n개의 엘리먼트들을 하나하나 모두 찾아보기 때문에 n번을 순회

	1	2	3	4	n
4	3	2	1	0	...
5	4	3	2	1	...
6	5	4	3	2	...
7	6	5	4	3	...
n	....	....	....	...

 

2안. 배열에서 최솟값과 최댓값을 찾아서 최대와 최소를 빼는 방식

	1	2	3	4	n
min	O	-	-	-	-
max	-	-	-	-	O

=> 시간 복잡도는 2*n = O(2n)

배열 안의 n개의 엘리먼트들 중 최솟값과 최댓값을 찾기 때문에 2번 배열의 순회!

 

3안. 맨 앞과 맨뒤의 수를 빼는 방법 

1

2

3

4

5

n

=> 시간 복잡도는 O(3)

배열 안의 n개의 엘리멘트들 중 맨 앞과 맨 뒤의 요소를 찾고 그 값을 뺌 (3번 일을 하죠? 그래서 3)

 

예시를 통해서 보면 값을 구하기 위한 연산의 횟수가 시간 복잡도라는 것을 이해할 수 있다.

표를 통해 본다면

	연산 회수	Big -O
1안	n^2	O(n^2)
2안	2n	O(2n)
3안	3	O(3)

3안의 경우를 constant(상수)라고 하는데 변수에 어떤 값이 들어와도 일정한 연산 회수를 통해 값을 얻을 수 있는 것이 가장 베스트.

그 와 반대로 n의 값이 크면 클수록 그만큼 많은 연산을 해야 한다는 의미로 워스트!

 

그래프로 확인해 본다면 (x = 문제의 크기 , y =시간)

(왼쪽 그레프) x = 문제의 크기 , y =시간

 

 

자료구조들의 시간복잡도. 

 

자료구조의 시간복잡도표를 보면 모두 각자 갖고 있는 장점과 단점이 있다.

완벽한 알고리즘은 없다는 것을 볼 수 있다.

효율적인 알고리즘을 구축하기 위해선 어떤 상황에서 어떤 방식이 사용되는 것이 좋고 안좋은지 

자료구조들의 특징을 잘 이해해하고 있어야 한다는 것을 이번 스프린트를 통해 알게되었다.