시간 복잡도(Time Complexity)

알고리즘에서의 시간 복잡도란 주어진 문제를 해결하기 위한 연산 횟수를 의미한다.

파이썬 프로그램에서는 2천만번 ~ 1억번의 연산을 1초의 수행 시간에 해결할 수 있다고 한다. 참고로 백준 사이트 기준으로 파이썬의 경우에는 2천만번의 연산당 1초의 수행 시간이 소모된다. ( CPU 보수적으로해서.. 1억번까지 1초라고 하기도 함.. )

시간 복잡도를 계산할 때는 보통 최악의 경우를 산정하고 계산한다. ( 대부분의 문제에서 최악의 경우를 테스트 케이스로 넣어뒀음 )

기초 TEST

import random

random_number = random.randrange(1,101)

for i in range(101) :
    if i == random_number :
        print(i)
        break

Quiz : 위의 코드에서 for문을 대상으로 따질 때, 최악의 연산 횟수와 최선의 연산 횟수는 몇일까?

• Answer

시간 복잡도 계산하기

시간 복잡도란 쉽게 말해 연산의 횟수라고도 볼 수 있다. 코드에서 연산의 대부분은 반복문을 통해 진행된다. 우리는 코드를 볼 때, for문과 while문에서 최악의 경우 몇 번의 연산이 진행되는 지를 파악하여 시간 복잡도를 계산할 수 있다. 우선 아래의 코드에서 연산 횟수를 파악해보자.

N = 100000
cnt = 1

for i in range(N):
    print(f"연산 {cnt}번째")
    cnt += 1

N = 100000
cnt = 1

for i in range(N):
    print(f"연산 {cnt}번째")
    cnt += 1

for i in range(N):
    print(f"연산 {cnt}번째")
    cnt += 1

for i in range(N):
    print(f"연산 {cnt}번째")
    cnt += 1

N = 1000000
cnt = 1

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

위처럼 연산 횟수는 매우 간단하게 계산할 수 있다. 그러나 위처럼 항상 연산 횟수가 상수로 결정되는 것은 아니다. 대부분의 문제는 입력 값인 N에 대해서 영향을 받아 연산 횟수가 계산된다.

즉 위의 3 문제는 N으로 변경되어 표현된다.

[문제 1] for문이 1개 → N번 연산

[문제 2] for문이 따로 따로 3개 → N번 * 3 = 3N번 연산

[문제 3] 2중 for문이 1개 → N번 * N번 = N^2번 연산

빅오 표기법

개요

우선 시간 복잡도를 표기하는 방법은 3가지가 있다.

1. Big-Ω(빅 오메가) - best case의 연산 횟수