크기 N과 크기 M의 시간 복잡도 계산

마지막으로 크기가 N과 M인 두 데이터로 연산할 때 이를 O(n²)으로 취급해야 하는지, 아니면 O(n)으로 취급해야 하는지에 대한 문제입니다. 적당하게 O(nm)으로 계산하는 경우도 많지만 정확하게 계산할수록 훨씬 유리합니다.

예를 들어 N과 M으로 for 문 연산을 한다고 가정하고 다음 코드를 짰습니다.

for i in N:
    for j in M:
        …

이런 상황이 생긴다면 무조건 O(n²)으로 취급해야 할까요? 경우의 수를 따져보는 게 편하겠죠. N의 값은 고정이고, M의 값이 변한다고 가정했을 때 발생하는 경우는 다음과 같습니다.

1. M이 매우 적은 숫자일 경우(~20), M의 연산은 사실상 상수 시간 이내로 끝나기 때문에 조금 연산이 큰 O(n)으로 봐도 무방합니다.

2. M이 어느 정도 큰 숫자일 경우(~100), N × M이 N²을 넘어서지 않는다면 N × M으로 계산해야 합니다.

3. M이 N과 거의 비슷하거나 매우 큰 숫자라면 입력 개수의 크기에 비례하는 것과 다름없으므로 이 시점부터는 O(n²)으로 취급해야 합니다.

문제를 풀기 전에 참고할 만한 사항은 이것이 전부입니다. 아직 소개하지 않은 특이 사항이나, 고려할 만한 것, 더 재미있는 참고 사항은 앞으로 여러 문제를 풀면서 하나씩 설명할 예정이니 끝까지 책을 읽어주세요. 그럼 코딩 테스트의 세계로 들어갑시다!