📌시간 복잡도

시간 복잡도?

시간 복잡도는 알고리즘의 효율성을 측정하는 중요한 척도 중 하나로, 알고리즘이 실행되는 데 걸리는 시간을 입력 크기와 관련지어 표현 것.
코딩 테스트에서 효율성을 묻는 문제는 문제 제한 사항에 명시되어 있는 조건을 극한으로 맞추는 입력 데이터를 사용해서 코드를 평가함.

 

빅오 표기법(Big O Notation)

시간 복잡도를 가장 일반적으로 나타내는 방법으로, 최악의 경우를 분석한 것.

 

주요 시간 복잡도 유형

1. O(1) - 상수 시간(Constant Time) : 입력 크기에 상관없이 실행 시간이 일정한 경우.
2. O(n) - 선형 시간(Linear Time) : 입력 크기에 비례해서 실행 시간이 증가하는 경우.
3. O(n^2) - 이차 시간(Quadratic Time) : 중첩된 루프를 사용하여 실행 시간이 입력 크기의 제곱에 비례하는 경우.
4. O(log n) - 로그 시간(Logarithmic Time) : 이진 탐색 알고리즘처럼 실행 시간이 입력 크기의 로그에 비례하는 경우.
5. O(n log n) - 선형 로그 시간(Linearithmic Time) : 합병 정렬(Merge Sort)이나 퀵 정렬(Quick Sort) 같은 효율적인 정렬 알고리즘에서 자주 나타나는 시간 복잡도.

시간 복잡도 그래프

 

입력 데이터 개수별 사용 가능한 시간 복잡도 알고리즘

입력 조건에서 명시되어 있는 최악의 경우를 시간 복잡도에 대입해보았을 때 1억이 넘지 않는다면 실행 시간이 1초보다 빠른 충분히 효율적인 코드일 가능성이 높다.
따라서 자신의 시간 복잡도에 문제의 제한 사항에 표기된 가장 큰 입력을 대입하여 계산하였을 때 아무리 커도 1억을 넘기지 않아야 시간 제한에서 안전한 코드이다.

* 단 여기에서 1억은 절대적인 기준이 아니다. 실제 계산한 수치가 1억 보다 작더라도 시간 제한에 걸릴 수 있다.
* 시간 제한이 걸려 있지 않은 문제라고 하더라도 대부분의 코드는 10초 이내에 실행 완료되어야 하며, 시간 복잡도를 계산한 결과가 10억이 넘어가면 다른 풀이를 시도할 것.