개념
프로그램을 잘 짰는지, 아니면 비효율적으로 짰는지 확인하는 방법 중 가장 단순하고 확실한 방법은 연산이 몇 번 진행되었는지 계산하는 것. 하지만, 코드가 길어지면 연산횟수를 세는 것에 많은 시간이 걸림. 따라서 코드의 실행 횟수를 일일이 세지 않고, 점근적 표기법을 사용함.
연산의 횟수를 점근적 표기법을 통해 추상적으로 표현하게 된 것이 시간복잡도!
보통 for loop을 1억번 도는데 걸리는 시간이 대략 1초.
제한시간이 1초인 경우에 대해 떠올린 솔루션의 시간복잡도를 O로 계산했을 때, N의 범위에 따라 제한 시간안에 올바른 답이 나오는 솔루션인지 빠르게 파악 가능
예시
알고리즘의 시간 복잡도를 입력 크기 N에 따라 계산할 때, 일반적으로 수행 가능한 연산 수의 범위는 아래와 같음.
N <= 10 (매우 작은 입력 크기)
- O(N!), O(2^N), O(3^N)과 같은 매우 높은 시간 복잡도도 계산 가능
N <= 20 (작은 입력 크기)
- O(2^N)와 같은 지수 시간 복잡도 계산 가능.
N <= 100 (중간 입력 크기)
- O(N^4)와 같은 다항 시간 복잡도 계산 가능.
N <= 500 (큰 입력 크기)
- O(N^3)와 같은 다항 시간 복잡도 계산 가능.
N <= 1,000 (매우 큰 입력 크기)
- O(N^2), O(N^2 log N) 이차 시간 복잡도, 이차 로그 시간 복잡도 계산 가능.
N <= 100,000
- O(N) 선형 시간 복잡도, O(N log N) 선형 로그 시간 복잡도, O(log N) 로그 시간 복잡도, O(1) 상수 시간 복잡도와 같은 낮은 시간 복잡도만 계산 가능
각 입력 크기에 대해 가능한 시간 복잡도를 계산할 때는, 일반적으로 현대 컴퓨터가 합리적인 시간 내에 처리할 수 있는 연산 수를 기준으로 함!
코딩 테스트 문제를 풀 때 모든 시간 복잡도를 외울 필요는 없습니다. 대신, 시간 복잡도와 입력 크기의 관계를 이해하고, 이를 문제 해결에 적용하는 방법을 익히는 것이 중요!
시간복잡도 이해
- 상수 시간 (O(1)): 매우 빠른 실행 시간, 입력 크기에 관계없이 일정.
- 로그 시간 (O(log N)): 입력 크기가 커질수록 느리게 증가, 이진 탐색 등에 사용.
- 선형 시간 (O(N)): 입력 크기에 비례해서 증가, 배열 순회 등에 사용.
- 선형 로그 시간 (O(N log N)): 병합 정렬, 퀵 정렬 등에 사용.
- 이차 시간 (O(N^2)): 입력 크기의 제곱에 비례해서 증가, 이중 루프, 버블 정렬 등에 사용.
- 지수 시간 (O(2^N), O(3^N)): 매우 빠르게 증가, 입력 크기가 작을 때만 사용 가능.
- 팩토리얼 시간 (O(N!)): 극단적으로 빠르게 증가, 입력 크기가 매우 작을 때만 사용 가능.
문제 예시
문제에서 N≤1000, N≤10^5이 주어짐.
- 입력 크기 파악 :
N≤1000, N≤10^5
- 적절한 시간복잡도 설정 :
N≤1000이라면 O(N^2), O(N^2 log N)이 적절.
N≤10^5라면 O(N), O(N log N), O(log N), O(1)이 적절.
- 알고리즘 선택 : 설정한 시간 복잡도에 맞는 알고리즘 선택
N≤10^5에서 정렬이 필요하다면 퀵 정렬이나 병합 정렬 O(N log N)을 선텍
https://www.codetree.ai/missions/6/problems/basic-time-complexity?&utm_source=clipboard&utm_medium=text