[알고리즘] 시간 복잡도(Time Complexity)

시간 복잡도란?

알고리즘이 n개의 입력 데이터로 문제를 해결하는 데 걸린 시간을 뜻합니다. 입력값이 커지면 처리 시간이 몇 배로 늘어나는지 확인해야 하며, 처리 시간이 빠른 알고리즘이 좋은 알고리즘입니다. 

 

최댓값 찾기 알고리즘의 시간 복잡도 판단해보기

1. 길이가 6인 1차원 배열의 원소를 순회하며 자신보다 큰 값을 모두 반환하는 코드입니다.

• 각 줄이 실행되는 것을 1번 연산된다고 생각하고 계산 
• for문(1) x for문(2) x if(3) 만큼 시간이 필요
• array의 길이를 N이라고 표현
• N의 크기에 따른 시간의 상관 관계를 시간복잡도라하므로 수식으로 표현
• N x N x 상수 = 상수 x N^2 = N^2 (N을 무한히 큰 수라 생각하면 상수 생략 가능)

array = [3, 5, 6, 1, 2, 4]         # 길이(N)이 6인 배열

for num in array:                  # array의 길이만큼 연산이 실행 (1)
        for compare_num in array:  # array의 길이만큼 연산이 실행 (2)
            if num < compare_num:  # 비교 연산 1번 실행 (3)
                break
            else:
            	return max_num

 

2. 길이가 6인 1차원 배열의 첫번째 원소의 값보다 큰 값을 반환하는 코드입니다.

• max_num 대입 연산 1번 
• (1) + for문(2) x (비교 연산(3) x 대입 연산(4))
• 1 + N x (1 + 1) = 1 + 2N = 2N

array = [3, 5, 6, 1, 2, 4]      # 길이(N)이 6인 배열

max_num = array[0]              # 연산 1번 실행 (1)

for num in array:               # array의 길이만큼 아래 연산이 실행 (2)
	if num > max_num:       # 비교 연산 1번 실행 (3)
		max_num = num   # 대입 연산 1번 실행 (4)

 

결과 비교

배열의 길이(N)에 따라 이중 for문(O(n^2))을 순회했을 때와 for문(O(n))을 순회했을 때 시간 복잡도를 비교한 표입니다. N과 N^2을 비교했을 때 N이 커질수록 더 큰 차이가 발생하는 것을 볼 수 있습니다. N의 크기가 커지면 상수는 시간 복잡도에 미치는 영향이 매우 작아 생략 가능하며 시간 복잡도가 얼마일까라고 추측할 때 입력값에 비례해서 N의 지수를 먼저 비교하면 알 수 있습니다. 

N의 길이	N^2	2N + 1
1	1	3
10	100	21
100	10000	201
1000	1000000	2001
10000	100000000	20001