Big O 정리

Big O  notation?  알고리즘의 속도를 표현한다. 

알고리즘의 속도를 어떻게 표현하는가 

 

컴퓨터는 각자  성능에 따라서 속도가 다르다. 

 

따라서 알고리즘의 속도는 완료까지 거치는 시간 자체가 아니라,

절차의 수로 표현함 

 

선형검색 알고리즘은  -> 한개씩 검색  20개 자료 -> 20개 스탭 이 소요된다.

input size =N 이면 N steps가 소요되는 것

 

이러한 경우

선형검색의 시간 복잡도 =O(N)라고 표현하며 ->'O of N'으로 발음한다. 

그리고 O(N)의 형태로 표현하는 것이 그 유명한 'Big O notation'이다.

 

 

---

Constant Time( 상수시간 ) -> N의 크기와 상관없이 steps가 정해진 알고리즘

let arr = [1,2,3,4]

function printFirst(arr){
	console.log(arr[0])
}

위와 같은 printFirst 함수는 

arr의 길이가 얼마나 늘어나던 상관없이 steps가 딱 한 번임 -> O(1)이라고 표현

 

이렇게 input(N의 크기)과 상관없이 steps의 크기가 결정되는 경우를 Constant Time (상수시간)이라고 한다. 

 

 

let arr = [1,2,3,4]

function printFirst(arr){
	console.log(arr[0])
	console.log(arr[0])
}

만약 이렇게  함수 내에 두 번을 출력한다고 해도 

시간복잡도는 O(1)이라고 표현함 

 

Big O notation에서는  러프하게 인풋의 크기에 따라서 함수가 어떻게 작동하는지만 고려함 

따라서 Big(O)에 따르면 상수(constant)는 고려되지 않음

 

만약 N크기와 상관없이 항상 100번의 스탭이 필요한 함수가 있다면 이 함수의 시간복잡도는 O(1)으로 표현됨

---

O(N) -> for와 같은 반복이 중첩없이 구성된 것  N에 따라 steps 증가

인풋이 증가하면 steps도 비례해서 증가한다.

만약 for문이 각각 두개가 병렬적으로 있다면 O(2N)으로 표현하지는 않는다. -> BigO는 상수는 무시하기에 !

---

O(N^2) ->Quadratic Time (2차 시간)

중첩이 반복이 있을 때 발생  

const function abc(arr){
	for(){
    		for(){
			// for 안에 for 이 중첩!
        	}
    	}
}

 

---

O(logN) -> Logarithmic Time (로그시간) : 이진검색 알고리즘을 표현

 

이진검색( ex. 우선순위 큐 , Heap , 완전이진트리 )의 시간복잡도는 O(logN) 으로 표현하며, 밑(base)은 생략한다. 

하지만 이진검색은 정렬되지 않은 배열에는 사용할 수 없다. 

따라서 O(logN) 시간복잡도를 얻고싶다면 정렬된 배열을 사용하도록 한다.