2.2.1 어림짐작해보기

먼저 ‘대략적으로 어느 정도 걸리겠다’라고 감을 잡는 일부터 시작해봅시다. 다음처럼 구구단을 계산하는 코드를 만들었습니다.

def printTimeTable(time):
    for i in range(1, 10):
        print("%d x %d = %d" % (time, i, time * i))

입력받은 단의 ×9까지만 출력하는 코드입니다. 여기에 입력 데이터가 무작위로 몇 만 개 주어진다면 이 프로그램의 시간 복잡도는 얼마일까요?

for 문을 하나 사용했기 때문에 O(n)인가요? 틀린 말은 아닙니다. 그렇다면 문제 조건을 조금 바꿔서 임의의 숫자부터 9단까지 구구단을 출력한다면 동일한 논리대로 O(n²)이 될까요?

def printAllTimeTable(time):
    for start in range(time, 10):
        for multiply in range(1, 10):
            print("%d x %d = %d" % (start, multiply, start * multiply))

직접 실행 시간을 확인해보겠습니다. 임의의 데이터 10만 개로 진행했으며, 순서대로 해당 구구단만 연산 → 해당 구구단부터 9단까지 전부 연산하는 순으로 실행했습니다. print() 함수를 연산 1번이라고 가정하고 얼마나 오랜 시간이 걸리는지 확인해봅시다.

NOTE