[알고리즘] 백 트래킹 알고리즘(back tracking), 빅 오 표기법(Big-O)

백트래킹

- 해를 찾는 도중 막히면 더 이상 깊이 들어가지 않고, 이전 단계로 되돌아가서 해를 찾아나가는 방법

- 최적화 문제와 결정 문제를 푸는 방법

- DFS 등으로 모든 경우의 수를 탐색하는 과정에서 조건문 등을 걸어 답이 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게 끔 구현가능

 

백 트래킹 vs DFS

백 트래킹 - 불필요한 탐색을 하지 않음

DFS -  모든 경우의 수를 탐색 

 

 

빅오 표기법

- 런타임과 메모리 사용을 최소화 방법

 

O(1)  constant time : for문 없이 바로 

O(log n)  log time : 이중 탐색

O(n)  linear time : for문

O(n log n)  log linear time : for문 안에 이중 탐색 - 퀵정렬, 병합 정렬, 힙 정렬

O(n^2) quadratic time : 이중 for문 - 문제를 해결하기 위한 단계의 수는 입력값  n의 제곱

O(n^3)  cubis time : 삼중 for문 

O(2^n)  exponential time : 상수값의 제곱 - n의 제곱되는 값 

O(n!) fibonnacci numbers : 피보나치 수열

 

시간 복잡도에서 갖게 되는 값과 크기 비교

O(N!) > O(2^n) > O(N²) > O(N log N) > O(N) > O(Log N) > O(1)