Big O notation
알고리즘을 푸는데 걸리는 최악의 시간
시간 복잡도
장기적으로 데이터가 증가함에 따른 처리시간의 증가율을 예측하기위해 만든 표기법 -> 상수는 무시함
ex) 이진탐색법으로 알고리즘을 푸는데 걸리는 시간은 O(logn)이다. 하지만 이진탐색법으로 모든 알고리즘 문제를 풀었을 때 O(logn)의 기간이 걸리는 것은 아니다. 만약 첫 탐색에서 답을 발견할 경우 걸리는 시간인 O(1)이기 때문이다. 따라서 Big O notation이라고 하면 어떤 방법으로 알고리즘을 풀었을 때 최대한으로 걸리는 시간이라고 할 수 있다.
O(1) : constant time
입력데이터(n)의 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘 시간복잡도
O(n) : linear time
입력데이터(n)의 크기에 비례해 처리시간이 걸리는 알고리즘 시간복잡도
O(n^2)
입력데이터(n)개가 각각 n번씩 돌면서, 데이터가 커질수록 처리시간이 길어지는 알고리즘 시간복잡도
O(logn)
이진탐색(binary search)의 시간복잡도로 한 번 단계를 거칠 때마다 처리시간이 절반씩 줄어드는 알고리즘 시간복잡도
입력데이터 n이 증가함에 따라 시간복잡도가 증가하기는 하나 그 증가속도가 점점 감소함 => O(1)다음으로 훌륭한 시간복잡도
oneThing