시간 복잡도 & 자료구조와 알고리즘이란?

자료구조와 알고리즘이란?

 

자료구조는 데이터의 구조이고,

알고리즘은 작업 과정의 묘사이다.

 

시간 복잡도 정의하기

 

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

 

시간 복잡도 유형

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

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

 

코딩 테스트에서는 빅 - 오 표기법 (O(n))을 기준으로 수행 시간을 계산하는 것이 좋다.

실제 테스트에서는 1개의 테스트 케이스로 합격, 불합격을 결정하지 않는다.

응시자가 작성한 프로그램으로 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 

합격으로 판단하므로 시간 복잡도를 판단할 때는 최악일 때를 염두에 둬야 한다.

 

다음 빅-오 표기법 (O(n))으로 표현한 시간 복잡도 그래프이다.

 

 

1번째 줄에 수의 개수  N( 1 <= N <= 1,000,000), 2번째 줄부터는 N개의 줄에 숫자가 주어진다.
이 수는 절대값이 1,000,000보다 작거나 같은 정수다. 수는 중복되지 않는다.

시간제한이 2초이므로 이 조건을 만족하려면 2억 번 이하의 연산 횟수로 문제를 해결해야 한다.
따라서 문제에서 주어진 시간 제한과 데이터 크기를 바탕으로 어떤 정렬 알고리즘을 사용해야 할 것인지를 판단할 수 있다.

연산 횟수는 1초에 1억 번 연산하는 것을 기준으로 생각한다.
시간 복잡도는 항상 최악일 때, 즉 데이터의 크기가 가장 클 때를 기준으로 한다.

연산 횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출

위 공식을 대입해 각 알고리즘이 이 문제에 적합한지 판단해 보겠다.

알고리즘 적합성 평가
버블 정렬 = (1,000,000) 의 2 제곱 = 1,000,000,000,000 > 200,000,000 -> 부적합 알고리즘
병합 정렬 1,000,000log 2 (1,000,000) = 약 20,000,000 < 200,000,000 -> 적합 알고리즘

문제에 주어진 시간제한이 2초이므로 연산 횟수 2억 번 안에 원하는 답을 구해야 한다.
버블 정렬은 약 1조 번의 연산 횟수가 필요하므로 이 문제를 풀기에 적합한 알고리즘이 아니라고 판단할 수 있다.
병합 정렬은 약 2,000만 번의 연산 횟수로 답을 구할 수 있으므로 문제를 풀기에 적합한 알고리즘이라고 판단할 수 있다.

이와 같이 시간 복잡도 분석으로 문제에서 사용할 수 있는 알고리즘을 선택할 수 있고,
이 범위를 바탕으로 문제의 실마리를 찾을 수 있다. 
즉, 데이터의 크기(N)를 단서로 사용해야하는 알고리즘을 추측해 볼 수 있다.

시간 복잡도를 바탕으로 코드 로직 개선하기

시간 복잡도는 작성한 코드의 비효율적인 로직(logic)을 개선하는 바탕으로도 사용할 수 있다.
이 부분을 활용하려면 가장 먼저 코드의 시간 복잡도를 도출할 수 있어야 한다.
시간 복잡도를 도출하려면 다음 2가지 기준을 고려해야 한다.

시간 복잡도 도출 기준
1. 상수는 시간 복잡도 계산에서 제외한다.
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.