(1) 복잡도란?

• 알고리즘의 성능을 나타내는 척도이다.
• 시간복잡도와 공간복잡도로 나눌 수 있다.
• 효율적인 알고리즘을 사용할 때 시간 복잡도와 공간 복잡도는 일종의 거래 상태가 유지된다.
  • 메모리를 조금 더 사용하는 대신 반복되는 연산을 생략하거나 계산의 복잡도를 줄일 수 있다.
  • 메모리를 더 소모하는 대신 시간을 비약적으로 줄이는 메모이제이션이있다.

(2) 시간복잡도

• 특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는지
• 알고리즘을 위해 필요한 연산의 횟수

빅오 Big-O

• 가장 빠르게 증가하는 항만을 고려하는 표기법이다.
• 함수의 상한만을 나타내는 것이다.

다음 예제는 5개의 입력을 받아 차례대로 5회 더해준다. 이 때, 연산 횟수는 N에 비례하는 것을 알 수 있다. 따라서 빅오표기법으로 시간 복잡도를 O(N)이라고 표기한다.

array = [3, 5, 1, 2, 4]
summary = 0

for x in array : 
	summary += x

print(summary)

아래 예시는 단순히 더하기를 수행하기 때문에 연산 횟수가 1이다. 따라서 상수 연산으로 O(1)로 시간복잡도를 표기할 수 있다.

a = 5
b = 7
print(a + b)

다음 예시는 O(N^2)의 시간 복잡도를 가진다. 2중 반복문을 통해서 곱셈 결과를 매번 출력하고 있기 때문이다.

array = [3, 5, 1, 2, 4]
for i in array :
	for j in array :
		temp = i * j
		print(temp)

하지만 퀵 정렬의 경우 평균 시간 복잡도는 O(NlogN)이지만 최악의 경우 시간 복잡도는 O(N^2)이다. 일반적으로 알고리즘 테스트에서는 최악의 경우에 대한 연산 횟수가 가장 중요하기 때문에 최악의 시간 복잡도를 우선적으로 고려해야한다.