시간복잡도

시간 복잡도란?

문제를 해결하기 위한 알고리즘의 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것은

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?라는 말이다.

 

효율적인 알고리즘을 구현한다는 것은 바꾸어 말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한

알고리즘을 구성했다는 말이다.

그리고 이 시간 복잡도는 주로 빅-오 표기법(Big- O)을 사용해 나타낸다.

 

Big- O 표기법이란?

최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다.

"최소한 특정 시간 이상이 걸린다" 혹은 이 정도 시간이 걸린다. 를 고려하는 것보다.

"가장 느릴 때 이 정도 시간까지 걸릴 수 있다"를 고려해야 그에 맞는 대응이 가능하다.

 

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가? 를 표기한 방법이다.

 

Big- O 표기법의 종류

1. O(1)

2. O(n)

3. O(log n)

4. O(n2)

 

1.O(1)

입력값의 크기와 관계없이 즉시 출력 값을 얻어낼 수 있다는 의미

입력값이 많더라도  즉시 값을 얻을 수 있다.

2. O(n)

선형 복잡도라고 부르며 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 형태

입력값이 많으면 그만큼 시간도 증가

3. O(log n)

이진 검색  속도와 같다고 생각하면 된다.

8개의 데이터를 탐색한다고 했을 때 찾고자 하는 수가 1일 때

이진트리는 절반인 1~4 또는 5 ~ 8 둘 중 하나의 노드를 탐색한다.

 

 다음 1~4 4개의 데이터에서 절반인 1~2 노드 중에 데이터를 찾는다.

따라서 문제를 해결하는 데 필요한 단계들이 연산마다 줄어듦

 

4. O(n ^ 2)

log n과 반대로 단계가 진행될수록 연산 횟수가 증가

이중 for문이라고 생각하면 된다.