시간 복잡도의 개념

코테 공부 전 반드시 알아야 할 두 가지

1. 시간 복잡도

2. 디버깅 

 

어떤 알고리즘으로 풀어야 할까?

- 알고리즘 선택의 기준이 되는 시간 복잡도 

 

코테의 핵심은 문제마다 주어진 시간 복잡도를 고려해 적절한 알고리즘을 선택하는 것.

처음 알고리즘을 잘못 선택하면 아무리 코드를 잘 짜려고 노력해도 좋은 결과를 거두기 어렵다.

문제를 본격적으로 풀어 보기 전에 시간 복잡도를 표기하는 방법과 활용하는 방법을 익혀본다. 

 

시간 복잡도 표기법 알아보기

알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 

일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다. 

 

시간 복잡도 정의하기

실제 시간 복잡도를 정의하는 3가지 유형은 아래와 같다.

• 빅-오메가(Ω(n)) : 최선일 때(best case)의 연산 횟수를 나타낸 표기법
• 빅-세타(Θ(n)) : 보통일 때(average case)의 연산 횟수를 나타낸 표기법
• 빅-오(O(n)) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법

시간 복잡도 예제 코드 : 0 ~ 99 사이의 값을 랜덤으로 선택하는 코드이다.

 

 

0 ~ 99 사이의 무작위값 찾아 출력하는 코드. 

빅-오메가 표기법의 시간 복잡도는 1번 (왜냐? best case의 연산횟수 표기법이니까, 최선의 경우 딱 1번)

빅-세타 표기법의 시간 복잡도는 N/2번 (average case의 연산횟수 표기법이므로)

빅-오 표기법의 시간 복잡도는 worst case의 경우이므로, N번이다.

 

코딩 테스트에선 어떤 시간 복잡도 유형을 사용해야할까?

코테에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋다. 

실제 테스트에서는 1개의 테스트 케이스로 합격, 불합격을 결정하지 않는다. 응시자가 작성한 프로그램으로 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격으로 판단하기 때문이다. 따라서 시간 복잡도를 판단할 때는 최악일 때worst case를 염두에 둬야 한다.