시간 복잡도와 데이터 크기

01-1 시간 복잡도 표기법 알아보기

알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 일반적으로 파이썬은 2000만 번~1억 번의 연산을 1초의 수행 시간으로 예측할 수 있다.

🔎 시간 복잡도 정의하기

시간 복잡도의 3가지 유형은 아래와 같다.
• 빅-오메가: 최선일 때(best case)의 연산 횟수를 나타낸 표기법
• 빅-세타: 보통일 때(average case)의 연산 횟수를 나타낸 표기법
• 빅-오: 최악일 때(worst case)의 연산 횟수를 나타낸 표기법

다음은 1~100 사이의 무작윗값을 찾아 출력하는 코드이다.

import random
findNumber = random.randrange(1, 101) # 1~100 사이 랜덤값 생성

for i in range(1, 101):
	if i == findNumber:
    	print(i)
        break

빅-오메가 표기법의 시간 복잡도는 1번, 빅-세타 표기법의 시간 복잡도는 N/2번, 빅-오 표기법의 시간 복잡도는 N번이다.

🔎 코딩테스트에서는 어떤 시간 복잡도 유형을 써야할까?

코딩테스트에서는 빅-오 표기법(O(n))을 기준으로 수행 시간을 계산하는 것이 좋다. 실제 테스트에서는 1개의 테스트 케이스로 합격, 불합격을 결정하지 않는다. 응시자가 작성한 프로그램으로 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격으로 판단하므로 시간 복잡도를 판단할 때는 최악일 때를 염두에 둬야 한다.

시간 복잡도는 데이터 크기(N)의 증가에 따라 성능(수행 시간)이 다르다.
O(n!) > O(2^n) > O(n^2) > O(nlogn) > O(n) > O(logn)

01-2 시간 복잡도 활용하기

🔎 알고리즘 선택의 기준으로 사용하기

버블 정렬 O(n^2), 병합 정렬 O(nlogn)

📌 문제 000) 수 정렬하기

시간 제한 2초, 백준 2750번

N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오.

입력

1번째 줄에 수의 개수 N(1 <= N <= 1,000,000), 2번째 줄부터는 N개의 줄에 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수다. 수는 중복되지 않는다.

5
5
2
3
4
1

출력

1번째 줄부터 N개의 줄에 오름차순 정렬한 결과를 1줄에 1개씩 출력한다.

1
2
3
4
5

시간 제한이 2초이므로, 이 조건을 만족하려면 4,000만 번 이하의 연산 횟수로 문제를 해결해야 한다.

따라서 문제에 주어진 시간 제한과 데이터 크기를 바탕으로 어떤 정렬 알고리즘을 사용해야 할 것인지 판단할 수 있다.

연산 횟수는 1초에 2,000만번 연산 기준, 시간 복잡도는 항상 최악일 때, 즉 데이터의 크기가 가장 클 때를 기준으로 한다.

연산 횟수 계산 방법

연산 횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출한다.

알고리즘 적합성 평가

• 버블 정렬 = (1,000,000)^2 = 1,000,000,000,000 > 40,000,000 : 부적합 알고리즘
• 병합 정렬 = 1,000,000log2(1,000,000) = 약 20,000,000 < 40,000,000 : 적합 알고리즘

버블 정렬은 약 1조 번의 연산 횟수가 필요하므로, 적합하지 않다.
병합 정렬은 약 2,000만 번의 연산 횟수로 답을 구할 수 있으므로 적합하다.

코드

N = int(input())
A = [0]*N

for i in range(N):
    A[i] = int(input())

for i in range(N-1):
    for j in range(N-1-i):
        if A[j] > A[j+1]:
            temp = A[j]
            A[j] = A[j+1]
            A[j+1] = temp

for i in range(N):
    print(A[i])

이와 같이 시간 복잡도 분석으로 문제에서 사용할 수 있는 알고리즘을 선택할 수 있고, 이 범위를 바탕으로 문제의 실마리를 찾을 수 있다. 즉, 데이터의 크기(N)를 단서로 사용해야 하는 알고리즘을 추측해 볼 수 있다.

🔎 시간 복잡도를 바탕으로 코드 로직 개선하기

시간 복잡도는 작성한 코드의 비효율적인 로직을 개선하는 바탕으로도 사용한다. 이를 활용하려면 코드의 시간 복잡도를 도출할 수 있어야 한다. 시간 복잡도를 도출하려면 다음 2가지 기준을 고려해야 한다.

시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 제외한다.
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

연산 횟수 = N

N = 100000
cnt = 1

for i in range(N):
	print("연산 횟수 " + str(cnt))
    cnt += 1

연산 횟수 = 3N

N = 100000
cnt = 1

for i in range(N):
	print("연산 횟수 " + str(cnt))
    cnt += 1
    
for i in range(N):
	print("연산 횟수 " + str(cnt))
    cnt += 1

for i in range(N):
	print("연산 횟수 " + str(cnt))
    cnt += 1

두 코드의 연산 횟수는 3배의 차이가 난다. 언뜻 생각하면 큰 차이인 것 같지만 코딩 테스트에서는 일반적으로 상수를 무시하므로 두 코드 모두 시간 복잡도는 O(n)으로 같다.

연산 횟수 = N^2

N = 100000
cnt = 1

for i in range(N):
	for j in range(N):
		print("연산 횟수 " + str(cnt))
    	cnt += 1

시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출하므로 이 코드에서는 이중 for 문이 전체 코드의 시간 복잡도 기준이 된다. 일반 for 문이 10개 더 있다 하더라도 도출 원리의 기준에 따라 시간 복잡도의 변화 없이 N^2으로 유지된다.

이와 같이 자신이 작성한 코드의 시간 복잡도를 도출할 수 있다면 실제 코딩 테스트에서 시간 초과가 발생했을 때 이 원리를 바탕으로 문제가 되는 코드 부분을 도출할 수 있고, 이 부분을 연산에 더욱 효율적인 구조로 수정하는 작업으로 문제를 해결할 수 있다.