알고리즘 정리1 : Big-O

Kimhojin_Zeno·2023년 3월 9일

Big O 공간복잡도 시간복잡도 알고리즘

알고리즘 정리

목록 보기

1/11

Big-O 시간복잡도

빅오 표기법(big o Notation)

시간복잡도(time complexity)

공간복잡도(space complexity)

빅오 표기법을 이용하여 각기 다른 알고리즘들의 시간복잡도와 공간복잡도를 평가한다.

같은 문제를 해결하는 여러 방법이 있을때 각 방법 중 어느 것이 베스트인지를 어떻게 평가하나?

빅오의 목적 → 여러가지 코드를 비교하고 성능을 평가하기 위해

빅오 표기법은 알고리즘이나 함수의 수행 시간 복잡도를 표기하는 방법 중 하나. 입력값의 크기에 따른 알고리즘의 성능을 나타내며, 보통 최악의 경우 시간 복잡도를 나타낸다. 빅오 표기법은 다양한 형태가 있지만, 가장 일반적인 형태는 O(1), O(log n), O(n), O(n log n), O(n^2). 이를 이용하여 여러 알고리즘의 성능을 비교하고 분석할 수 있다. 시간 복잡도 뿐만 아니라 공간 복잡도를 나타내는 데에도 사용된다.

O(1)은 입력값의 크기와 상관없이 일정한 실행 시간을 가지는 알고리즘. 예를 들어, 배열에서 인덱스를 이용해 요소를 찾는 경우다. 이 경우, 배열 전체를 탐색하지 않고도 원하는 요소를 즉시 찾을 수 있으므로 실행 시간이 일정하다. O(1) 알고리즘은 가장 효율적인 알고리즘 중 하나이며, 상수 시간 알고리즘이라고도 불린다.
O(log n)은 입력값의 크기가 커질수록 실행 시간이 조금씩 증가하는 알고리즘이다. 이진 검색 알고리즘 등이 이에 해당. 이 알고리즘은 입력값을 절반씩 나눠가며 탐색하기 때문에, 탐색 대상이 2배씩 증가해도 실행 시간이 크게 증가하지 않는다. 탐색 알고리즘, 효율적 정렬 알고리즘도 마찬가지다. 재귀함수에서는 공간복잡도가 이렇다.
O(n)은 입력값의 크기에 비례하여 실행 시간이 증가하는 알고리즘. 예를 들어, 배열에서 모든 요소를 순차적으로 탐색하는 경우. 이 경우, 배열의 크기가 커질수록 실행 시간도 커지므로 O(n) 알고리즘은 대부분의 상황에서 효율적이지 않다.
O(n log n)은 입력값의 크기가 커질수록 실행 시간이 더 빠르게 증가하는 알고리즘. 병합 정렬, 퀵 정렬 등이 이에 해당한다. 이 알고리즘들은 입력값을 반씩 나눠가며 정렬하고, 마지막에 합치는 과정에서 O(n)의 시간이 추가로 소요. 따라서 O(n log n) 알고리즘들은 일반적인 정렬 알고리즘 중에서 가장 빠른 속도다.
O(n^2)은 입력값의 크기의 제곱에 비례하여 실행 시간이 증가하는 알고리즘이다. 버블 정렬, 선택 정렬 등이 이에 해당. 이 알고리즘들은 입력값을 반복해서 비교하고 교환하기 때문에, 입력값이 커질수록 실행 시간이 기하급수적으로 늘어나게 된다. 따라서 O(n^2) 알고리즘들은 입력값이 작을 때는 효율적이지만, 입력값이 커질수록 실행 시간이 급격하게 증가해 비효율적이다.

상수는 무시한다.

O(2n) → O(n) 이다.

O(1000n+50) → O(n)

O(500) → O(1)

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

O(n^2 + 5n + 8) → O(n^2)

산수는 금방이다.

변수 선언도 금방이다.

배열이나 객체에 인덱스로 접근하는것도 금방이다.

루프는 루프의 길이 곱하기 루프 안에 있는 연산들.

루프 안에 루프가 있으면 n^2이다.

코드 시간 재기

좋은 코드란?

속도가 빠른
메모리를 적게 쓰는
읽기에 쉬운

보통 1,2번을 주로 본다. 3. 읽기에 쉽게 쓴것이 1,2번을 희생할때도 있다. 조율하는 것이 중요.

시간 재는 법

function addUpTO(n) {
	let total = 0;
	for(let i = 1; i <= n; i++) {
		total += i;
	}
	return total;
}

let t1 = performance.now();
addUpTo(1000000000);
let t2 = performance.now();
console.log(`Time Elapsed: ${(t2-t1) / 1000} seconds.`)

performance.now(); 는 브라우저에서 해당 코드가 걸렸을때 시간을 나타냄.

쓴 코드 앞뒤로 배치하고 걸린 시간을 구해서 1000으로 나누면 밀리세컨드로 측정가능.

그런데 이렇게하면 실행하는 기기에 따라, 환경에 따라 측정값이 달라짐.

매번 이렇게 하기도 어렵다.

그래서 시간이 아닌 연산의 갯수를 센다.

function addUpTo(n) {
	return n * (n + 1) / 2;
}

// 곱하기1회, 더하기 1회, 나누기 1회

n의 값이 크든 작든, n의 값과 상관 없이 연산이 3번 이루어진다.

function addUpTO(n) {
	let total = 0;
	for(let i = 1; i <= n; i++) {
		total += i;
	}
	return total;
}

그러나 앞에 for문을 사용한 코드는 n의 값에 따라 n번만큼 더하므로 n갯수의 연산이다.

‘+’연산과 ‘=’도 연산이다. i++도 연산이다. ≤로 비교하는 것도 연산. 하나하나 세는것보다는 전체적인 그림이 중요하다. n이 커지면 커질수록 연산의 갯수도 커진다는 것.

공간복잡도

입력이 커질수록 알고리즘이 얼마나 많은 공간을 차지 하는가

공간 = 메모리

여기서 공간은 인풋이 아닌 알고리즘 자체가 필요로 하는 공간

공간복잡도 → 보조 공간 복잡도(auxiliary space complexity)

booleans, numbers, undefined, null은 불변 공간이다.
문자열은 O(n) 공간을 필요로 한다. n은 문자열의 길이. 길이가 50인 문자열은 길이가 1인 문자열의 50배 공간.
reference타입, 배열, 객체도 O(n)이다.

배열, 오브젝트 성능평가

배열과 오브젝트의 성능

배열 알에 데이터를 추가하는 것이 왜 안좋은가

내장 메소드의 성능 등

객체의 빅오

객체: 정렬되어 있지 않은 키:값 데이터 구조

객체는 정렬되어 있을 필요가 없을때 잘 작동한다.

빠른 접근, 입력과 제거를 원할때 좋다.

입력,제거,접근하는 시간이 상수. O(1)

탐색은 O(n)이다. key를 찾는 것이 아닌 어떤 특정 정보가 어떤 값에 있는지 확인하는 것.

메소드들.

Object.keys, Object.values, Object.entries → O(n)

hasOwnProperty → O(1)

배열의 빅오

정렬되어 있다는 점이 다르다.

searching → O(n)

Access → O(1) 접근은 바로 된다. 뒤에 인덱스라고해서 더 느려지는게 아님.

입력과 제거는 복잡하다.

입력 : 맨 뒤에 추가할때 → O(1) 상수다. 객체에 추가하는 것과 다를게 없다. 복잡하지 않음.

앞에 추가할때 → O(n) 맨 앞에 넣고 뒤에 모든 인덱스를 새로 배정해야 한다.

앞에것을 제거하는것도 마찬가지다. 복잡함.

배열의 앞에 추가하거나 제거하는 것은 최대한 피해야한다. 효율적이지 않음.

push와 pop이 shift와 unshift보다 빠르다.

다 외울 필요는 없음

push : O(1)
pop : O(1)
shift : O(n)
unshift : O(n)
concat : O(n)
slice : O(n)
splice : O(n)
sort : O(n*log n) 나머지보다 더 복잡. 제일 복잡하다.
forEach, map, filter, reduce, etc : O(n)

정리

객체는 거의 모든 것을 빠르게 하지만, 정렬되어 있지 않음

배열은 정렬되어 있지만, 끝에 추가하고 제거하는 작업만 빠르다. 앞에 넣거나 빼면 처음부터 끝까지 모두 영향을 주면서 인덱스를 다시 정리해야한다. 중간에 넣거나 빼는것도 똑같다. 그 위치뒤로는 전부 영향을 받는다.

Kimhojin_Zeno

Developer

다음 포스트

알고리즘 정리1 : Big-O