입력 길이에 따라 알고리즘이 처리하는 시간을 정량화한 것이다. 일반적으로 빅오 표기법을 사용한다. 빅오 표기법이란, 식의 최고 차항을 제외한 모든 항과 최고차항의 계수를 제외시킨다.
일반적으로 문제를 풀 때 시간 제한이 1초라면 시간복잡도는 다음과 같다.
- N범위가 500인 경우: 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 풀 수 있다.
- N범위가 2000인 경우: 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 풀 수 있다.
- N범위가 100000인 경우: 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 풀 수 있다.
- N범위가 10000000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계하면 풀 수 있다.
참고 자료
이것이 취업을 위한 코딩 테스트다 with 파이썬