복잡도(Complexity)

복잡도는 알고리즘의 서능을 나타내는 척도이다. 복잡도는 시간 복잡도와 공간 복잡도로 나눈다.

시간 복잡도란

시간 복잡도란 입력 크기에 따라 알고리즘이 동작하는 데 걸리는 시간을 분석하는 것입니다. 알고리즘의 성능을 분석하기 위한 지표입니다.

일반적으로, 알고리즘의 시간 복잡도는 입력 크기 n에 대한 연산 횟수 f(n)의 함수로 나타내어집니다. 이 때 연산 횟수는 기본적인 연산(덧셈, 뺄셈, 곱셈, 나눗셈, 비교 등)이 수행되는 횟수를 말합니다.

알고리즘의 시간 복잡도는 다음과 같은 표기법을 사용하여 표현할 수 있습니다.

채점 환경

파이썬은 C/C++에 비해 동작 속도가 느리다. 그래서 파이썬을 선책했을 때는 C/C++에 비해 2배의 수행 시간 제한을 적용하기도 한다. 2020년을 기준으로 파이썬 3.7로 코드를 작성할 때, 자신의 코드가 1초에 2,000만번 의 연산을 수행한다고 가정하고 문제를 풀면 실행 시간 제한에 안정적이다. 사실 수행 시간을 정확히 측정하기 위해서는 채점 시스템의 컴퓨터 사양과 사용하는 알고리즘을 면밀히 분석해야 하는데, 일반적인 기업 코딩 테스트 환경에서는 파이썬으로 제출한 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하면 크게 무리가 없다는 점만 기억하자. <나동빈, "이것이 코딩 테스트다", 108쪽>

시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도 O(NlogN)이내의 알고리즘을 이용하여 문제를 풀어야 한다. 실제로 N = 1,000,000일 때 Nlog2N은 약 2,000천만이기 때문이다. 따라서 알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인한 뒤에 이 문제를 어느 정도의 시간 복잡도의 알고리즘을 작성해야 풀 수 있을 것인지 예측할 수 있어야 한다. <나동빈, "이것이 코딩 테스트다", 108쪽>

O표기법

O 표기법은 알고리즘의 최악의 시간 복잡도를 정의합니다. 다시 말해 함수의 상한만을 나타낸다.

예를 들어, O(n)은 입력값에 대해 n번의 연산을 한다는 것을 의미합니다.

시간 복잡도 분석의 필요성 : 알고리즘의 성능에따라 입력값에대한 연산횟수가 달라집니다. 이러한 알고리즘의 성능을 미리 예측하고 최적화 하기 위해서는 시간 복잡도에 대한 이해와 분석이 필수적입니다.

대입, 출력과 같은 대부분의 연산의 횟수는 상대적으로 N이 커짐에 따라서 무시할 수 있을 정도로 작아진다. ‘실제 코딩 테스트’에서는 차수가 작은 항드을 완전히 무시하는 것은 곤란하다.

예를 들어, 3N^3 + 5N^2 +100,000인 알고리즘이 있을때, 빅오 표기법 에서는 차수가 큰 항만 남아서 O(N^3)로 표기할 수 있지만 실제로 N이 작을때는 상수값인 100,000의 영향이 매우 커진다. 그렇기에 빅오 표기법은 항상 절대적이지 않다는 것을 기억하자.

복잡도의 종류