반응형
위 이미지는 시간복잡도를 나타낸 이미지다.
시간복잡도는 알고리즘 로직을 코드로 구현할 때 입력값에 따라 요구되는 시간을 나타낸 것이다. 그리고 이것을 표현하기 위해 표기법이 존재하는 데 이것을 Big-O 표기법이라고 한다.
- Big-O : 최악의 경우
- Big-Ω : 최선의 경우
- Big-θ(빅-세타) : 평균의 경우
프로그램의 상태 상황에 따라 편차가 존재할 수 있는데, 이때 최악의 경우를 가정해서 시간을 계산함으로써 최악의 상황을 피하기 위함이다.
Big-O 표기법
- O(1) : 데이터와 관계없이 일정한 시간이 소요됨
- O(log n) : 데이터가 많아 질 수록 시간이 증가되지만 BTS처럼 노드 이동시마다 절반씩 줄어들어 줄어듦
- O(n) : 데이터가 많아질수록 linear 하게 증가 ( 비례하여 증가 )
- O(n^2) : 데이터가 많아질수록 배로 시간이 증가
- O(C^n) : 데이터가 많아질 수록 exponential하게 기하급수적으로 증가
효율적인 알고리즘이란!?
- 예를들면 적은 데이터를 가지고 효율적인 알고리즘을 짜기 위해 굳이 시간과 공을 들여 노력할 필요가 없다는 뜻이며, 필요한 상황에 맞게 최적화 하는 것
반응형
'IT 정보 > Java' 카테고리의 다른 글
[Java] 완전 탐색 알고리즘 (Brute-Force Algorithm) (7) | 2022.05.31 |
---|---|
[Java] 탐욕 알고리즘 (Greedy) (16) | 2022.05.30 |
[Java] Optional Class (14) | 2022.05.28 |
[Java] 스트림 (Stream) (스트림 생성) (6) | 2022.05.28 |
[Java] 스트림 (Stream) 최종 연산 (terminal operation) (22) | 2022.05.28 |