저별이의 초보 코딩

코딩을 위해 코드를 짜다보면 시간복잡도를 고려해야 한다는 것을 한번씩 듣게 된다.

시간 복잡도란 무엇일까?

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

이것은 효율적인 알고리즘을 구현하기 위해서 사용하게 되는데 주로 빅-오 표기법을 사용한다.

이 Big-O 표기법에는 크게 5가지가 있다.

1. O(1)

2. O(n)

3. O(log n)

4. O(n2)

5. O(2n)

1. O(1): 일정한 복잡도, 입력값이 증가하더라도 시간이 증가하지 않음.

printf("time");

말 그대로 값을 넣으면 즉시 나온다는 것이다.

계산하기 위해 반복을 돌릴 필요가 없다는 얘기이다. 즉시 나오기 때문에 1이 시간복잡도를 가진다.

2. O(n): 선형복잡도, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미함.

for i in range(n):
	printf("hello")

입력값(n)이 늘어나는 만큼 동일한 비율로 증가하는 것을 의미한다. 입력값이 많으면 많을수록 시간이 더 오래걸릴것이다. 늘어난다고 무조건 O(n)인 것은 아니다. 입력값이 증가할 수록 같은 비율로 증가해야 한다.

1이 늘어날 때 걸리는 시간이 5초씩 더 늘어난다면 O(5n)이 되므로 선형복잡도라고 할 수 있다.

3. O(log n): 로그 복잡도로 빅오 표기법 중 O(1)다음으로 빠른 시간이 소요

이것을 이해하기 위해서는 탐색 기법을 떠올려보아야 한다.

리스트 혹은 배열에서 찾을 때 up, down으로 숫자를 맞춰나가는 과정을 생각하면 된다.

전체를 탐색해야 하는 것보다 절반으로 줄어들기 때문에 빠르게 탐색을 할 수 있다. 

이 예시로는 이진 탐색 트리를 생각하면된다.

트리에서 두개 이상으로 계속해서 갈라지는 것을 반복하다보면 원하는 값에 도달할 수 있다.

4. O(n2): 2차 복잡도, 입력값이 증가함에 따라 시간이 n의 제곱수 만큼 걸리는 것을 의미

for i in range(n):
	for j in rnage(n):
    	print("hello")

입력을 했을때 제곱값만큼 걸리게 되면 이 복잡도에 해당한다고 할 수 있다.

예를 들면 이중 for문이라고 할 수 있을 것이다.

생각을 해보게되면 for문이 0부터 4까지 5번씩 반복하는게 이중,삼중으로 하게 되면 제곱, 세제곱으로 걸리게 된다. 이렇게 증가하게 되는 것을 2차 복잡도라고 한다. 이 예시에서느 반복횟수가 같지만 만약에 다르다면 시간복잡도는 O(nm)이런 형태로도 될 것이다.

5. O(2n): 기하급수적 복잡도. 가장 느린 시간 복잡도

def fibo(n):
	if n<=1:
    	return 1
    fibo(n-1)+fibo(n-2)

n=int(input())
fibo(n)

이 복잡도 식에서 볼 수 있는 것처럼 기하급수적으로 굉장히 늘어난다는 것이다. 대표적인 예시로는 재귀가 있다. 재귀는 반복해서 호출하기 때문에 기존보다 몇배씩 증가할 수 밖에 없고 그래서 시간 역시 오래 걸리는 구조가 되게 된다.

이 5가지가 시간 복잡도의 대표적인 사례이다. 이외에도 여러가지 복잡도가 존재한다.

알고리즘, 자료구조를 학습하게 되면 이 복잡도가 보이게 되고 고려하게 된다. 

지금 완전히 이해하기 보다는 알고리즘 개념과 관련 코드를 보다보면 자연스럽게 이해가 될 것이라고 예상한다.

-참고자료

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/