빅오란?

함수를 수행하는데 걸리는 시간, 공간을 표기하는 것이다.

빅오 표기법

O(N), O(N*log N), O(N), O(log N), O(1)

어떤 컴퓨터든 연산의 개수는 달라지지 않으므로 연산의 개수가 중심이 되고 단순화 하여 포현한다.

let n = 5;
		// 1번.     2번.    3번.
for (let i = 0; i < n; i++ ){  // 연산 = , < , + , =
		// 4번.
	i = i + 1;  // 연산 + , - 
	console.log(i);
}

위 와 같은 코드의 빅오 표기법은 O(N)이다. 연산의 개수는 총 6개 이다.

1번 부분은 코드를 수행하는데 1번만 이루어진다.
2번은 n번 만큼 연산(<)을 수행, 3번은 n번 만큼 연산( +, = )을 수행, 4번은 n번 만큼 연산( +, = )을 수행한다.

따라서 2,3,4 번은 5n, 1번을 합치면 이 코드블록의 연산의 수는 5n+1이 된다. 아주아주 큰 수가 입력이 되었을 경우에도 어차피 n에 따라 증가하기 때문에 빅오표기법은 이를 단순화하여 O(N)으로 표기한다.

빅오 표기법을 사용하는 이유

시간은 항상 연산의 개수와 관련이 있고 알고리즘의 성능을 비교하기 위해 사용한다.

공간복잡도

위 내용까진 시간복잡도에 대해 빅오표기를 한 것이고, 공간복잡도는 얼만큼의 메모리를 확보하는지 나타내는 것이디.

변수의 변화? 개수?로 계산하면 된다.

const addList = function (arr){
	const newArr = [];
	for(let i = 0; i < arr.length; i++){
		newArr.push(2 * arr[i]);
	}
	return newArr;
}

위 코드의 공간복잡도는 O(N)이다. 입력의 갯수(n)에 따라 newArr의 공간이 n만큼 늘어나기 때문이다.

시간복잡도는 O(N)

시간 복잡도 연산의 개수이다. 얼마만큼의 연산이 이루어지는지를 나타낸 것이다.

잘못인식하고 있던 점

for문 같이 반복문을 기준으로 n이라고 생각했더 이중for문이면 n2..

연산이 얼마나 이루어지냐가 시간복잡도를 결정하는 것 이었다.

function (n) {
	for (let i = 0; i < Math.min(5, n); i++) {
		console.log(i);
	}
}

위 코드를 보면 for문이 있다고 시간 복잡도가 n이 아니고 입력된 n이 얼마나 큰 숫자든 작은수든 최대 5번 최소 n번 만큼 반복이 되어 시간복잡도는 상수이다.O(1)

알고리즘이란?

문제를 해결하는 방법이다.
좋은 알고리즘을 고르기 위해 성능 평가를 하는데 성능 평가의 기준은 빅오 표기법으로 비교할 수 있다.
상황에 따라 또는 어느것을 중요하게 보냐에 따라 좋은 알고리즘의 선택은 달라질 수 있다.

배열

배열은 정렬 되어있지만 끝에 추가, 삭제 하는것은 시작에 추가, 삭제보다 훨씬 빠르다.

끝에 추가(push), 삭제(pop) 는 시간 복잡도가 O(1) 상수이다. 접근도 상수이다.(인덱스)

탐색 O(N) 이다.

정렬 O(N * log N)을 제외한 나머지 메서드들은 O(N)이다.

객체

객체는 정렬되어있지 않지만 거의 모든게 빠르다.

탐색 O(N)을 제외한 입력, 삭제, 접근 O(1) 이다.