복잡도

알고리즘을 작성을 해서 목표하는 기능이 구현되는 것은 가장 우선시 되어야할 사항이지만 

같은 기능을 구현하더라도 효율의 차이가 발생한다.

알고리즘에서는 크게 2가지로 효율성을 판단하며 이를 복잡도라고 한다. 

복잡도의 종류는 시간복잡도, 공간복잡도가 있다. 

 

복잡도

시간복잡도

알고리즘을 수행하는 시간을 말하며 입력받은 값에 따라 항상 달라지기 때문에 입력받은 값을 기준으로 표기를 한다.

예를 들어 다음과 같은 알고리즘 이라면 

# 배열 생성
a_list = [1,4,2,7,9,4,3,6,3]


# 각 리스트원소를 순회하면서 3을 찾아 출력하는 알고리즘
for i in a_list:
	if i == 3:
		print(3)
		break

각 리스트원소들을 모두 꺼내 확인해야하므로 배열의 길이에 따라 값이 시간이 달라진다. 

2개면 2번, 3개면 3번 바반복.. 물론 찾는 값이 일찍 나온다면 전부 확인할 필요는 없으니 예상된 숫자보다 일찍 나온다 

하지만 복잡도를 따질때는 항상 최악의 경우를 생각해서 판단해야한다. 따라서 내가 찾고자 하는 값이 가장 끝에 있을 경우를 생각하면 최대 배열의 길이까지 전부 봐야한다. 그 말인즉슨 list의 내부 원소 개수를 N개 라하면 N번 순회해야한다. 

이처럼 입력값에 따라 시간 복잡도를 판단하게 된다. 

 

시간 복잡도의 표기는 다음과  같다

O(1) 

O(N)

O(logN)

O(NlogN)

O(N^2)

O(N!)

 

O(1)의 시간 복잡도는 상수시간복잡도라하여 가장 빠른 시간복잡도를 의미한다. 

해당 복잡도가 나오는 함수들은 대부분 조회하거나 출력, 간단한 사칙연산 등등 있다. 

코드 한줄이라고 생각하면 이해하기 쉽다

 

O(N)은 앞에서 예를 들었던 LIST 확인 처럼 입력한 값의 크기에 따라 정비례하여 커지는 것으로 

보통 반복문을 한번 사용했을 때 적용된다 

 

O(logN), O(N logN) 갑자기 Log가 나와서 당황스럽지만 이는 이후에 정리할 트리구조나 이진탐색 알고리즘을 알게 되면 이해가 되는 시간 복잡도로 반복문을 사용하지만 과정 중 특정 조건에 의해 매우 짧아지는 경우를 의미한다 

예를들면 최대값을 찾는 방법들에도 여러 방법이 있지만 단순한 생각으로는 각 원소들을 전부 확인해가면서 비교하는 방법이 있을 것이다 이는 각 리스트들의 원소를 전부 확인해야하므로 시간복잡도는 O(N)이라할 수 있다. 

하지만 해당 리스트가 정렬되어있다고 가정한다면 술게임으로 자주 했던 UP/DOWN 방법으로 찾게되면 모든 리스트 원소들을 확인하지 않더라도 최대값을 찾을 수 있다. 자세한 설명은 이후에 정리할 에정이다.

O(N^2) 은 입력받은 값의 제곱에 비례하는 시간 복잡도로써 보통 이중 방복문을 사용할 때이다. 

O(N!) 은 매우 큰 시간 복잡도로 해당 시간 복잡도가 나온다면 해당 알고리즘은 구현할 수 없다라고 생각된다. 

또한 시간 복잡도에서 알아야할 점은 세세한거에 신경을 쓰지 않는다는 것이다. 

예를 들어 다음과 같은 코드일 때 

#python 

a_list = [ 1, 2, 4, 5, 6 ]  # 입력 N 

a = a_list[0] + a_list[2]	# 사칙연산 : O(1)

b = a_list[1] + a_list[4]	# 사칙연산 : O(1)
	
c = a + b				# 사칙연산 : O(1)

print(c)				# 전체 시간복잡도 : O(1) + O(1) + O(1)  = O(3)???

 

주석에 나와있는 것처럼 각각의 연산의 시간 복잡도가 O(1)이고 세번 반복했으니 전체 시간 복잡도는  O(3)인가? 라고한다면 정확하게 따지자면 맞는 소리이다. 하지만 시간복잡도의 종류가 나누어진 것처럼 세세하게 판단하는 것이아니라 대략적인 감을 판단한는 것이기 때문에 해당 알고리즘의 시간 복잡도는 O(1)이라 표현한다. 

그 외에도 반복문을 별개로 2번썻다고해서 O(N) + O(N) = O(2N)이 되는 일은 없고 해당 알고리즘의 시간 복잡도는 O(N)이다.

대략적인 감을 찾는데에 집중하자 

 

 

공간 복잡도

 

공간에 대한 효율성을 판단하는 방법으로 해당 알고리즘에 사용되는 자원에 대한 내용이다. 

시간 복잡도와는 다르게 별도의 표기할 수 있으나 시간복잡도에 비해 크게 신경을 쓰지 않는 것 같다.