시간 복잡도와 연산량

시간 복잡도와 연산량

알고리즘 문제를 풀이할 때, 제한 조건에 시간 제한이라는 것이 존재한다.
작성한 알고리즘이 의도한 결과를 잘 만들어 낼 수 있다고 해도 제한 시간 안에 결과를 내지 못하면 안된다는 것이다. 그러기 때문에 우리는 알고리즘을 작성하기 전에 내가 작성할 알고리즘의 시간 복잡도를 계산하여 제한 시간 안에 결과를 만들어 낼 수 있는지 검증해야 한다.
이를 위해서는 내가 사용할 라이브러리나 알고리즘의 시간 복잡도를 알고 있어야 한다. 그러면 이들을 종합한 시간 복잡도를 확인하여 내가 작성할 알고리즘이 제한 시간 범위 안에 있다는 것을 검증할 수 있게 된다.

빅오(Big-O) 표기법

알고리즘의 입력 크기가 충분히 클 때, 최악의 경우를 기준으로 가장 영향력 있는 항만 남겨서 표기하는 방법

알고리즘의 시간 복잡도를 표현하는 방법으로는 최상의 경우를 표현하는 오메가(Ω), 평균적인 경우를 표현하는 세타(Θ), 최악의 경우를 표현하는 빅오(O) 표기법이 있다.
코딩 테스트에서는 이 3가지 중 빅오 표기법(O)을 기준으로 시간 복잡도를 계산한다.
빅오 표기법은 _데이터의 입력값이 충분히 크다고 가정하고, 연산과 관련된 코드들을 기준_으로 계산한다.
표기에서는 _상수항이나 영향력이 없는 항은 무시하고 가장 큰 항만을 남겨서 표현_한다.

시간 복잡도별 가능한 초당 연산 횟수 - PyPy3 기준

• O(1): 상수 시간
• O(logN): 로그 시간(약 1억)
• O(N): 선형 시간(약 2000만)
• O(NlogN): 로그 선형 시간(약 500만)
• O(N^2): 이차 시간(약 5만)
• O(N^3): 삼차 시간(약 300-500)
• O(2^N): 지수 시간(약 15)
• O(N!): 팩토리얼 시간(약 8)
• O(N^N): N의 N제곱 시간(약 3)

O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N) < O(N!) < O(N^N)

일반적으로 파이썬은 java나 c++보다 연산 속도가 느리다. 그래서 루프나 동일 함수를 반복 호출하는 등과 같이 반복하여 사용하는 코드가 많은 경우에 PyPy3를 사용하는 것이 유리하다. PyPy3는 JIT(Just-In-Time) 방식을 활용하여 자주 쓰이는 코드를 컴파일하여 캐싱한다. 이로 인해 더 빠른 성능을 낼 수 있지만 메모리 사용량이 더 높고 시작 시간이 길다. 간단한 코드인 경우 CPython이 더 유리하다.

시간 복잡도 계산법

• 변수 선언은 제외한다.
• 가장 바깥쪽 반복문부터 시간 복잡도를 계산한다.
• 반복문 안에 있는 연산의 시간 복잡도를 계산하여 더한다.
• 중첩 반복문일 경우, 두 반복문의 범위를 곱한다.
• 모든 연산의 시간 복잡도를 합산하여 최종 시간 복잡도를 구한다.
• O(3N)에서 상수항인 3은 제외하고 O(N)으로 표현한다.
• O(2N^2 + 5N + 3)에서 영향력이 없는 5N + 3과 상수항을 제외하고 O(N^2)으로 표현한다.