시간복잡도
- 알고리즘의 성능을 나타내는 지표로, 입력 크기에 따른 연산 횟수를 의미한다
- 입력 크기는 알고리즘이 처리해야 할 데이터의 양이다
- 시간복잡도는 낮을 수록 좋다
시간복잡도를 측정하는 방법
- 연산 횟수와 관련이 있다
- 시간복잡도는 알고리즘이 시작한 순간부터 결과값이 나올 때까지의 연산 횟수를 나타낸다
- 최선, 보통, 최악의 경우로 나뉜다
1차원 배열 검색으로 연산횟수 비교
- 연산 횟수가 가장 적은 경우는 배열의 첫번째 위치이다
- 연산 횟수가 가장 많은 경우는 배열의 마지막 위치이거나 찾는 값이 없는 경우이다
알고리즘 수행 시간을 측정하는 방법
- 절대 시간을 측정하는 방법(말 그대로 시간을 측정 but 프로그램 실행 환경에 따라 달라질 수 있어서 활용 x)
- 시간 복잡도를 측정하는 방법(연산 횟수와 관련)
10칸짜리 배열에서 시간 복잡도 측정
- 최선의 연산 횟수: 1
- 최악의 연산 횟수: 10
- 그러나 이러한 1과 8은 특정한 입력 크기에 따른 연산 횟수로 시간 복잡도를 이야기 하는거는 특정 상황에 한한 것으로 무의미하다
- 예를 들어 배열의 크기가 1이라면 최선, 보통, 최악의 경우는 모두 1이다
코딩테스트에서 알고리즘 성능 측정 2가지
- 최악의 경우를 고려하자
- 알고리즘 성능은 정확한 연산 횟수가 아닌 추이를 활용하자
우리가 알고 싶은 것은 정확한 연산 횟수가 아니라 내 알고리즘이 제한 시간 안에 수행될 수 있는 지 정도만 파악하면 된다(왜? 우리가 구하려는 것은 상한의 정확한 값이 아닌 이정도 될것이다를 파악하는 추이이기 때문)
- 이러한 방식으로 충분히 큰 입력값 N에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방법을 점근적 표기법이라고 한다
최악의 경우 시간 복잡도를 표기하는 빅오표기법
- 가장 많이 사용하는 점근적 표기법은 상한선을 활용하는 방법인데 이 표기법을 빅오 표기법이라고 한다
- 빅오표기법은 최고차항만 남기고 최고차항에서도 계수를 지우면 된다
시간 복잡도를 코딩 테스트에 활용하는 방법
- 코딩 테스트의 문제는 1000~3000만 정도 고려해서 시간 복잡도를 생각하자
- 예를 들어 제한 시간이 1초인 문제는 연산 횟수가 3,000만이 넘는 알고리즘은 사용하면 안된다
