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

시간 복잡도

• 주어진 문제를 해결하기 위한 연산 횟수
• 일반적으로 파이썬 프로그램에서는 2000만 번 ~ 1억 번의 연산을 1초의 수행 시간으로 예측 가능

시간 복잡도 정의하기

시간 복잡도 유형

• 빅-오메가($\Omega(n)$): best case의 연산 횟수
• 빅-세타($\Theta(n)$): average case의 연산 횟수
• 빅-오($O(n)$): worst case의 연산 횟수

예시

import random

findNumber = random.randrange(1,101) # 1 ~ 100 사이의 난수 생성
# print(findNumber)

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

• 빅-오메가($\Omega(n)$): 1
• 빅-세타($\Theta(n)$): N/2
• 빅-오($O(n)$): N

코딩 테스트에서 사용되는 시간 복잡도 유형

• 빅-오($O(n)$) 표기법을 기준으로 수행 시간을 계산하는 것이 좋음
• 코딩 테스트에서는 응시자가 작성한 프로그램으로 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야한 합격으로 판단함
  • 최악일 때(worst case)를 염두에 둬야 함

시간 복잡도 그래프

⇒ 데이터 크기(N)의 증가에 따라 성능(수행 시간)이 다르다는 것을 확인할 수 있음