[ Do it! 알고리즘 코딩 테스트 ] 1일차 _ 01. 시간 복잡도

해당 포스팅은 " Do it! 알고리즘 코딩 테스트 " 기반으로 정리 하였습니다

 

💡 시간 복잡도 ( Time Complexity )

 : 주어진 문제를 해결하기 위한 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도

 : 1억 번의 연산을 1초의 수행 시간으로 예측할 수 있음

 

💡시간 복잡도 표기 종류

: 시간 복잡도(성능 측정)에 사용되는 표기법은 3가지로 나눠 구분한다.

 

🔸Big-Omega (빅 -  오메가) : 최선일 때의 연산 횟수를 나타낸 표기법 , Ω(n)

🔸Theta (빅 - 세타) : 보통일 때의 연산 횟수를 나타낸 표기법, θ(n)

🔸Big-O (빅 - 오)  : 최악일 때의 연산 횟수를 나타낸 표기법, O(n)

 

💡코딩 테스트에서는 어떤 시간 복잡도를 사용하는가?

: 코딩 테스트에서는 Big-O을 기준으로 수행 시간을 계산하는 것이 좋다.

=> 코딩 테스트를 할 땐 최악일 때를 염두해둬야한다.

 

빅 오 표기법의 경우 실제 연산이 걸리는 시간보다는 증가율에 따라 표현을 하며 데이터 크기(N)의 증가에 따라 성능( 수행시간)이 다르다는 것을 확인할 수 있다.아래는 빅 오 표기법에서 사용되는 시간 복잡도에 따른 그래프이다.

https://www.youtube.com/watch?v=4iqlPfhW17g / 시간 복잡도 성능 지표

 

O(1) < O(log n) < O(n) < O(n×log n) < O(n2) < O(2n)

의 수식으로 표기 되며 순서대로 아래와 같은 이름으로 불린다.

 

상수 시간 복잡도 < 로그 시간 복잡도 < 선형 시간 복잡도 < 선형 로그 시간 복잡도 < 2차 시간 복잡도 < 지수 시간 복잡도

 

💡시간 복잡도 활용

🔶 연산 횟수 계산법

1초에 1억 번 연산하는 것을 기준

시간 복잡도는 항상 최악일 때, 데이터의 크기가 가장 클 때를 기준을 한다.

 

주어진 시간이 2초 일 경우 연산 횟수 2억 번안에 원하는 답을 구해야한다.

버블 정렬과 병합정렬을 기준으로 예시를 아래와 같이 확인을 할 수 있다.

 

버블 정렬 - O(n2) 

병합 정렬 - O(n log n)

 

버블 정렬 - (1,000,000)2 > 200,000,000 ( 부적합 )

병합 정렬 - 1,000,000log2(1,000,000) < 200,000,000 ( 적합 )

 

이처럼 시간 복잡도 분석으로 사용할 수 있는 알고리즘을 선택하고 문제를 해결하며 코드 로직을 개선 할 수 있다.

 

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

코드의 시간 복잡도를 도출할 수 있으면 코드 로직 개선이 가능하다.

 

🔶 시간 복잡도 도출법

❶ 상수는 시간 복잡도에서 제외

❷ 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준

 

연산 횟수 N

int main()
{
	int n = 100000;
    int cnt = 0;
    
    for(int i = 0; i < n; i++)
    {
    	System.out.println("연산 횟수 : cnt++");
    }
}

 

연산 횟수 3N

int main()
{
	int n = 100000;
    int cnt = 0;
    
    for(int i = 0; i < n; i++)
    {
    	System.out.println("연산 횟수 : cnt++");
    }
    
    for(int i = 0; i < n; i++)
    {
    	System.out.println("연산 횟수 : cnt++");
    }
    
    for(int i = 0; i < n; i++)
    {
    	System.out.println("연산 횟수 : cnt++");
    }
}

 

두 예제 코드의 연산 횟수는 3배 차이가 나지만 ❶ 과 같이 상수는 무시하므로 두 코드 모두 시간 복잡도는 O(n)으로 같다.

 

int main()
{
	int n = 100000;
    int cnt = 0;
    
    for(int i = 0; i < n; i++)
    {
     	for(int j = 0; j < n; j++)
        {
        	System.out.println("연산 횟수 : cnt++");
        }       	
    }
}

 

❷ 과 같이 가장 많이 중첩된 반복문을 기준으로 도출된다. 이중 for문이 전체 코드의 시간 복잡도가 되며 일반 for문이 여러개 있더라도 N^2가 유지된다.