• 효율적인 알고리즘에 대한 생각 = 시간 복잡도에 대한 생각
• 시간복잡도란? 문제를 풀기 위한 알고리즘의 논리를 코드로 구현할 때 시간복잡도를 고려하는 것은 ‘입력값의 변화에 따라 연산을 수행할 때 연산수에 비해 시간이 얼마나 걸리나요?‘.
• 시간 복잡도를 표현하는 방법Big-O(상위 점근선, 최악), Big-Ω (큰 오메가, 낮은 점근선(최고)), 빅세타(빅세타, 평균). 최고와 평균을 고려하여 시간을 계산하기보다 ‘최악의 경우를 대비하라‘하는 것이 바람직하다 Big-O 표기법이 많이 사용됩니다.
• Big-O 표기법의 유형
1. 오(1) : 복잡도가 일정하여 입력값이 증가해도 시간이 증가하지 않습니다.
2. 오(엔) : 선형 복잡도, 입력 값이 증가함에 따라 시간도 같은 비율로 증가합니다.
3. O(log n) : 대수복잡도, Big-O 표기법 중 O(1)에 이어 두 번째로 빠른 시간복잡도.
전) 데이터 구조의 BST(Binary Search Tree)에서 원하는 값을 검색할 때 노드가 이동할 때마다 경우의 수가 절반으로 줄어듭니다.
감소하다
4. 오(n^2) : 2차 복잡도, 입력값이 증가함에 따라 n의 거듭제곱 비율로 시간이 증가함
전) 입력값이 1일 때 1초가 걸렸던 알고리즘이 입력값이 5일 때 25초가 걸린다면, 이 알고리즘의 시간 복잡도는 O(n^2)로 표현됩니다.
5 . 오(2n) : 지수복잡도, Big-O 표기법 중 가장 느린 시간복잡도
전) 피보나치 수열
※참고 사이트