반응형 Big O1 빅오(Big O) 시간복잡도 [ Big O, 시간복잡도 ] 빅오(Big O) 시간복잡도는 위 그림하나도 전부 설명이 가능하다. 빅오는 처리시간이 아니라 시간의 증가율을 나타낸다고 보면 된다. X는 데이터의 갯수, Y는 처리의 갯수이다. 순서를 보면 $O(2^n)$ > $O(n^2)$ > $O(n log n)$ > $O(N)$ > $O(log n)$ > $O(1)$ 이다. 참고로 빅오 표기법에서 상수는 연산에 고정된 값이라서 연산에 크게 작용하지 않는다고 본다. 그래서 상수 10을 빅오랑 곱해도 값은 빅오 그대로 라는 것을 알아야 한다. 예를들어 $10 \times O(1)$ = $O(1)$ 이다. 시간 증가량에 대한 표기법은 점근적 상한(Upper Bound)인 Big-O 외에 점근적 일치(Tight Bound)인 Big-Theta.. 2021. 4. 10. 이전 1 다음 반응형
