시간 복잡도

1.1 O(n)인경우

 

ex) 집합의 크기가 10일때, {1,2,3,4,5,6,7,8,9,0} x를 잡합의 왼쪽부터 오른쪽으로 검사하면

-> 마지막 0이 x 라면 10번 다해야함

-> 이런 경우 n번 연산해야하기 때문에 o(n)

 

1.2 O(log^n) 인경우

 

ex) 이분 탐색

트리 구조가

1. 왼쪽 서브트리의 모든 값은 루트 노드의 값보다 작습니다.
2. 오른쪽 서브트리의 모든 값은 루트 노드의 값보다 큽니다.

이럴때, 6을 기준으로 n을 찾을 때, 2개씩은 무조건 제외할수있기때문에 log2N

-> 하지만 2N과 10N 둘다 그래프 모형은 비슷해서 표현은 무방 

 

1.3 O(n^2) 인경우

 

집합 크기가 4이며, 집합에 들어있는 수가 1.2.3.4 일때 ->

두수를 합하여 5가 되는 경우는 몇가지 인가? ->

최악의 경우 n*n개 

 

1.4 O(2^n) 인 경우

 

ex)