2023.01.31

📖오늘 배운  것

빅오 표기법

: 입력된 내용이 늘어날수록 알고리즘의 실행 시간이 어떻게 변하는지 설명하는 방식

-> 정확한 수치라기 보다 전반적인 추세애 대한 개념

-> 실행시간이 갖는 최대치를 의미한다.

 

O(2n) → O(n)

O(500) → O(1)

O(13n^2) → O(n^2)

앞에 붙는 상수, 혹은 뒤에 붙는 상수는 없애서 단순화하여 표현한다. 수치가 커졌을 때 그래프 모양에서 차이가 크지 않기 때문이다.

 

1. 산수(나눗셈, 곱셈, 뺄셈, 덧셈...)은 상수시간이 거린다.

2. 변수 처리도 상수시간이 걸린다.

3. 배열에서 인덱스로 값을 찾는 것도 상수시간이 걸린다.

4. 루프가 있으면 루프의 길이x 루프 안에 있는 연산들 만큼의 시간이 걸리고 중첩루프가 있으면 n 제곱이 될 수 있다.

빅오를 계산할 땐 시간복잡도와 공간복잡도로 나눌 수 있다.

 

공간 복잡도

1. boolean, numbers 등은 모두 상수이다.

2. 문자열은 길이만큼 공간을 차지한다.

3. 배열이나 객체도 길이만큼 공간을 차지한다.

 

let total = 0;
for(let i = 0; i<=arr.length; i++) {
	total += arr[i];
}

시간복잡도가 아닌 공간복잡도로 생각했을 때,

변수 total은 number로 상수 공간을 차지한다. 변수 i도 number로 상수 공간을 차지한다. 반복문을 볼면서 total의 값이 변화하지만  number는 상수 공간을 차지하므로 변화가 없다. 즉 O(1)의 공간복잡도를 가진다.

 

let total = [];
for(let i = 0; i<=arr.length; i++) {
	total.push(arr[i]);
}

배열의 경우 total 변수에 선언된 배열은 반복문에 의해 추가되는 값의 개수에 따라 차지하는 공간이 달라진다. 즉, arr의 길이 b에 따라 차지하는 공간이 달라지므로 O(n)의 공간복잡도를 가진다.

 

 

 

 

💭배운 점

 

대강 알고 있던 빅오 표기법에 대해 다시 개념부터 정립할 수 있었다. 시간복잡도에 대한 것만 알고있었는데 공간복잡도도 있다는 것을 알게 되었다. 강의에서 이야기 한 것처럼 시간복잡도가 안좋아도 공간복잡도가 상수시간인 알고리즘도 있는 것처럼 목적에 따라 어떤 것을 중요시 할 것인지가 달라질 것 같다. 

지금은 간단한 식에 대한 계산만 가능하지만 점점 알고리즘에 익숙해지면 복잡한 로직도 스스로 시간복잡도나 공간복잡도를 계산할 수 있을까? 앞으로 배울 내용이 궁금하다.

 

 

 

출처: 유데미 강의: https://www.udemy.com/course/best-javascript-data-structures/