시간 복잡도

가장 효율적으로 해결하는 알고리즘이 각 코테 문제에 존재한다.

우리는 여러 알고리즘 중 당연히 문제를 빠르게 푸는 알고리즘을 선택해야 한다.
그렇다면 어떤 것을 기준으로 알고리즘을 선택해야 할까? -> 바로 '시간 복잡도'를 보고 선정해야 한다.

 

시간 복잡도

 

• 시간 복잡도란, 알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미한다. 시간 복잡도는 낮으면 낮을 수록 좋다.
• 입력크기는 쉽게 말해서, 알고리즘이 처리해야 할, 데이터 양이라고 생각하면 된다. 책장에 꽂혀있는 5권의 책을 정리해야 하는 문제라면, 이때의 입력 크기는 5가 된다.

 

1차원 배열 검색하기

• 값을 가장 빨리 찾는 경우
  • 검색 시작 위치에 찾을 값이 바로 있는 경우이다. = 연산 비교 횟수가 최소임
• 값을 가장 늦게 찾는 경우
  • 아예 찾으려는 값이 없거나, 가장 마지막에 위치하는 경우 = 연산 비교 횟수가 최대임

 

알고리즘 수행 시간 측정 방법

• 절대 시간을 측정하는 방법
  • 말 그대로 시간을 측정하면 된다.
  • ex) 배열에서 검색하는 프로그램을 작성한 다음, 프로그램을 실행하여 결과가 나올 때까지의 시간을 측정하면 된다.
  • 하지만, 이 방법은 실행 환경에 따라 달라질 수 있기 때문에 코테에서는 잘 활용하지 않는다.
• 시간 복잡도를 측정하는 방법
  • 검색 문제에서 언급한 '연산 횟수'와 관련이 있다.
  • 즉, 시간 복잡도는 알고리즘이 시작한 순간부터 결과값이 나올 떄까지의 연산 횟수를 나타낸다.
  • 그리고 시간 복잡도를 측정한 결과는 (best, normal, worst)의 경우로 나눈다.
  • 하지만, 배열의 크기가 1일 경우 best, normal, worst는 모두 연산 횟수가 1이므로 의미가 없음.
  • 따라서 이 결과만 보고 이 알고리즘은 모든 경우에 연산 횟수가 1인 성능을 가지는 것이구나라고 생각하면 안됨.
  • 즉, 특정 입력 크기에 한하여 연산 횟수를 기준으로 시간 복잡도를 측정하면 안되고, 입력 크기를 N으로 일반화하여 연산 횟수의 추이를 나타내야 한다.
  • 이런 방식으로 입력 크기에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방법을 점근적 표기법이라고 한다.
  • 그리고 코테에서는 모든 경우의 수에서 알고리즘이 문제를 처리하는 것을 고려해야 하므로 시간 복잡도는 최악의 경우를 가정하여 이야기 하는 것이 일반적이다.

 

최악의 경우 시간 복잡도를 표현하는 빅오 표기법

• 빅오 표기법을 가장 많이 사용한다.
• 함수의 최고차항을 남기고 계수를 지워 표기하면 된다. O(...)
• 최고차항을 지우는 작업의 우선순위는 다음과 같다.
  • 지수함수 > 다항함수 > 로그함수

 

시간 복잡도를 코딩 테스트에서 활용하는 방법

• 코테에서는 제한 시간이 존재한다. 문제를 분석한 후에 빅오 표기법을 활용해서 해당 알고리즘을 적용했을 때 제한 시간 내에 출력값이 나올 수 잇을지 확인해볼 수 있다.
• "컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억 번이다."
• 연산 횟수는 1,000~3,000만 정도로 고려해서 시간 복잡도를 생각하면 된다.
• ex) 제한 시간이 1초인 문제는 연산 횟수가 3,000만이 넘는 알고리즘은 사용하면 안된다. 제한 시간이 1초인 문제에 각 시간 복잡도별로 허용할 수 있는 N의 범위를 생각한다