알고리즘

알고리즘- 빅오, 시간복잡도, 공간복잡도

Okguri 2022. 5. 29. 15:19

Big O

-빅오는 왜 필요할까?

  • 알고리즘은 기본적으로 문제를 해결하기 위해 필요한 것. 코드를 일반화하고, 코드의 상대적 성과를 비교하는 방법이 빅오.
  • 어떤 것이 좋은 코드일까? 빅오는 코드의 수준을 상/중/하 등으로 판단한다.
  • 왜 코드가 최고여야만 하지? 그냥 작동만 하면 안 되나? → 아주 많은 양의 데이터를 다룰 때를 생각해 보자. 그때의 성능 차이는 수많은 차이를 많들어냄.
  • 또한 빅오는 버그 수정하려고 할 때, 문제점뿐만 아니라 처리 속도를 늦추는 원인을 이해하는 데 도움을 준다. 즉, 비효율적인 부분을 찾는 데 도움이 된다.
  • 어떤 함수가 제일 나은지 등 문제가 면접에 나오기도 하니, 빅오 표기법을 배워두자!

예시

1부터 n까지 전부 더하는 코드를 만들어야 할 때

  • 1부터 n까지 반복문을 돌리는 코드
  • n(n+1)/2 를 리턴하는 코드

무엇이 더 나은가?

→ 더 낫다는 기준은 무엇인가? 속도? 메모리 낭비? 가독성?

좋은 코드 : 빠르지만 메모리를 많이 잡아먹지 않고, 가독성도 있는. 이 세 개의 균형을 잡아야.

-그렇다면 속도는 어떻게 재야 할까?

개발자도구에서 가볍게 시간 재는 거. 
let t1 = perpormance.now(); //수행 시간 알려주는 코드 
함수 실행 ex) upToCase(10000);
let t2 =  perpormance.now();
console.log((t1-t2)/1000);

그러나 값 매번 바뀜. 정확하지 않음.
  • 다른 기계에서 측정한다면, 다른 시간값을 기록한다는 문제가 있다.
  • 같은 기계에서도 매번 측정 결과가 다르다는 문제가 있다.
  • 너무 빠른 알고리즘은 속도 측정이 정확하지 않을 수 있다.
  • 실행하는 데 1시간이 걸리는 알고리즘이라면, 하나하나 실행하면서 시간을 보내야 한다.
  • 그렇다면 어떻게 코드의 속도를 잴까? → 여기서 빅오 표현의 필요성이 나온다.

속도를 재는 것의 대안은? → 연산 갯수를 세기.

ex. n * (n+1)/2 의 경우 연산을 세 번 하는 거.

연산이 많으면 많을수록 속도는 느려진다.

또한 숫자가 커지면 커질수록, 속도가 느려진다. 숫자와 속도가 반비례함.

예컨대 for문으로 1부터 n까지의 합을 구한다고 할 때, 합을 구하려면 n번 만큼의 for문을 돌려야 한다. 따라서 n이 커지면 커질수록 속도가 올라갈 수밖에 없음.

빅오? input 크기와 실행시간의 관계를 말함. =⇒ 시간복잡도와 관련

input 숫자가 커질수록 알고리즘 런타임(실행시간)이 어떤 결과를 갖는지 설명하는 방식.

to talk formally about how the runtime of an algorithm grows as the inputs grow

빅오에서 worst 란? 가장 시간이 오래 걸리는 것.

그러니까, input을 크~게 넣었을 때 알고리즘의 실행시간이 어떻게 변화하는지를 봐야하는 거임. 기억해야 할 거는 input과 runtime 인 것임.

O(1) : input이 얼마든 항상 runtime이 비슷함.

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

O(n) : input이 커질수록 runtime도 비례하며 증가

fucntion(n){
	total = 0;
		for(let i = 0; i < n; i++){
				total += i;
		}
	return total;
}

기본적으로 연산은 n번만큼 해야 함. for문이 n번 돌아가기 때문. for문 안에서 더하기 등 추가 연산이 있긴 하지만, 무한으로 생각하면 n앞의 정수는 의미가 없어지기 때문에 O(n)으로 표현.

fucntion(n){
	total = 0;
		for(let i = 0; i < n; i++){
				total += i;
		}
		for(let j = 0; j < n; j++){
				total += j;
		}
	return total;
}

for문이 두 번 돌아가지만, O(n)이다. 2n이라고 생각할 수 있다.

O(n^2) : input이 커질수록 runtime은 제곱으로 비례하며 증가

fucntion(n){
		for(let i = 0; i < n; i++){
			for(let j = 0; j < n; j++){
				console.log(i,j);
			}
		}
}

n 안에 또 n이 들어간 중첩 for문. n이 3이면 9번의 연산을 기본으로 하고, n이 10이면 100번의 연산을 기본으로 한다. 이 같은 연산을 빅오 표기법으로 하면 O(n^2). 가장 느린 방법이다.

빅오는 결국 추세. 무한 개념을 생각하면 된다. 무한으로 가면 상수는 다 나가떨어지고 변수만 남음!

빅오의 규칙(늘 맞는 건 아니고, 보통 이렇게 사용한다는 거)

  1. 사칙연산 : O(1)
  2. 변수할당 : O(1)
  3. 배열에서 key나 index로 값을 찾는 방식 : O(1)
  4. 루프에서 빅오찾기 : 루프 길이(n) * 루프 안 연산 개수(x) = O(x * n)이 된다. 하지만 결국 최종적으로 표기하는 건 O(n)

O(2n) → O(n)

O(500) → O(n)

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

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

속도

O(1) < O(log n) < O(n) < O(n logn) < O(n^2)

공간복잡도 : 메모리를 얼마나 사용하는가

rules

  1. booleans, numbers, undefined, null의 공간은 변하지 않는다.
    • true, false가 차지하는 공간 크기는 같고, 1과 10000이 크기도 동일하다.
  2. string은 O(n)의 자리를 차지한다. String이 클수록 공간복잡도도 비례하게 커진다.
  3. 배열, 객체(Reference types)도 O(n). n은 배열 길이, 객체의 키 수라고 여기면 된다.
    • 길이가 2인 배열보다 길이 4인 배열이 차지하는 공간이 더 크다.

결국 string의 길이와 객체의 길이를 신경써야 하네.

늘까먹는 로그...

$log_2(8)=3$

$2^3=8$

2 몇승의 값이 8이 되나요?의 답 = 로그

지수함수와 로그함수는 역함(inverse) 관계다.

보통 알고리즘에서는 $log_2 === log$ 로 표기한다.

O(log n) : 엄청 좋다. O(1)보다 살짝느리다. 거의 비슷한 수준이다.