알고리즘 - 알고리즘 복잡도

알고리즘 복잡도

알고리즘 복잡도란 알고리즘의 성능을 나타내는 척도로 시간 복잡도와 공간 복잡도로 나눌 수 있습니다.

 

시간 복잡도

시간 복잡도란 프로그램의 입력값과 연산 수행 시간과의 상관관계를 나타내는 척도입니다.

쉽게 설명하면, 문제를 해결하기 위한 알고리즘의 필요 연산 횟수로 생각해 볼 수 있습니다.

 

시간복잡도는 보통 빅오 표기법을 이용해 나타냅니다.

 

빅오(Big-O) 표기법

빅오 표기법은 알고리즘이 수행될 때 걸릴 수 있는 최악의 실행 시간을 나타냅니다.

빅오 표기법을 사용하는 이유로는 최악의 실행 시간을 나타내야 알고리즘이 최소한으로 보장하는 성능을 알 수 있기 때문입니다.

 

빅오 표기법은 다음과 같이 나타냅니다.

 

 

N은 가장 큰 수만 빅오 표기법에 표기됩니다.

• 예시
  • O(N) : 5N + 3, 2N +10logN , 10N
  • O(N^2) : N^2+2N+4

 

알고리즘 문제를 풀 때, N(입력)의 크기를 이용해서 대략 문제가 요구하는 시간복잡도를 유추할 수 있습니다.

 

 

공간 복잡도

공간 복잡도란 입력의 크기와 문제를 해결하는데 필요한 알고리즘의 필요 메모리 공간의 상관관계를 의미합니다.

쉽게 말해, 문제 해결을 위한 메모리 사용량으로 이해하면 됩니다.

 

공간 복잡도도 빅오 표기법을 이용해 나타냅니다.

 

요새는 컴퓨터들의 메모리 용량이 크기 때문에 공간복잡도의 중요성은 시간 복잡도 보다 떨어진다고 볼 수 있습니다.

 

 

알고리즘 문제 풀 때 Tip

• 입력값의 범위를 보고 시간복잡도로 알고리즘 추측하기
  • 연산 횟수는 1초에 1억 번 연산을 기준
  • 시간복잡도는 항상 최악인 데이터의 크기가 가장 클 때를 기준으로 설정
• 실수 연산이 들어간다면 되도록 double이나 BigDecimal로
• 실수 비교 시 , 등호 사용 X
• 알고리즘 별 시간복잡도를 알고 있는 것이 좋음