[Java] 시간 복잡도 (Time Complexity)

위 이미지는 시간복잡도를 나타낸 이미지다. 

시간복잡도는 알고리즘 로직을 코드로 구현할 때 입력값에 따라 요구되는 시간을 나타낸 것이다. 그리고 이것을 표현하기 위해 표기법이 존재하는 데 이것을 Big-O 표기법이라고 한다. 

• Big-O : 최악의 경우
• Big-Ω : 최선의 경우
• Big-θ(빅-세타) : 평균의 경우

프로그램의 상태 상황에 따라 편차가 존재할 수 있는데, 이때 최악의 경우를 가정해서 시간을 계산함으로써 최악의 상황을 피하기 위함이다. 

Big-O 표기법 

• O(1) : 데이터와 관계없이 일정한 시간이 소요됨
• O(log n) : 데이터가 많아 질 수록 시간이 증가되지만 BTS처럼 노드 이동시마다 절반씩 줄어들어 줄어듦 
• O(n) : 데이터가 많아질수록 linear 하게 증가 ( 비례하여 증가 )
• O(n^2) : 데이터가 많아질수록 배로 시간이 증가 
• O(C^n) : 데이터가 많아질 수록 exponential하게 기하급수적으로 증가

 

효율적인 알고리즘이란!?

- 예를들면 적은 데이터를 가지고 효율적인 알고리즘을 짜기 위해 굳이 시간과 공을 들여 노력할 필요가 없다는 뜻이며, 필요한 상황에 맞게 최적화 하는 것