절반씩 버리면서 찾았을때
θ(logN) : 찾는게 없을때 , Ω(logN) : 한번에 찾았을때
평균 O(logN)
하나의 인풋으로 이중 for 문이 돌때
θ(N²)
두개의 인풋으로 for문이 각각 돌때
θ(N + M)
두개의 인풋으로 이중 for문이 돌때
θ(N * M)
시간복잡도 시간비교
O(1) < O(logN) < O(N) < O(N*logN) < O(N²) < O(2ⁿ) < O(N!)
O 빅오를 많이 쓰는 이유!
일반적으로 가장 많이 걸리는 경우만 알아도 충분
다른 바운드를 계산하기 귀찮아서
괜히 최솟값으로 말했다가 태클걸릴까봐
주위에서 다들 그렇게 쓰니까
모르고 쓰니까?