시간 복잡도와 공간 복잡도

시간복잡도란?

- 문제를 해결하는데 걸리는 시간과 입력의 함수 관계

- 시간복잡도를 이용하는 알고리즘 분석은 알고리즘의 성능이 얼마나 효율적인지 알 수 있는 가장 일반적인 방법이다.

- 어떠한 알고리즘의 로직이 얼마나 오랜시간이 걸리는지 를 나타내는데 쓰인다.

- 알고리즘의 로직이 최악의 경우 걸리는 실행시간을 나타내며 이것을 보통 빅오 표기법으로 나타낸다.

빅오 표기법이란?

• 입력 범위 n을기준으로 해서 로직이 몇번 반복되는지 나타내는 것

• 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지 항을 없앤것

 

빅오 표기법을 쉽게 적용할 수 있는 규칙

- 덧셈, 뺼셈, 곱셈, 나눗셈과 같은 산수는 상수이다, 상수시간에 포함된다.

    • n의 값이 상관이 없다. 10이들어오든 100이 들어오든 1억이 들어오든 컴퓨터가 처리하는 시간은 비슷하다.

- 변수 배정도 상수이다.

    • x = 1, x = 1000과 같이 컴퓨터가 변수에 값을 배정하는데 걸리는 시간은 비슷하다.

- 배열에서 인덱스 첫번째의 아이템은 찾는것과 10번째 아이템을 찾는것과 똑같은 시간이 걸린다.

- 객체를 다루고 객체를 다루기위한 키가 있다면 상수시간이다.

- 루프가 있다면 루프의 길이 곱하기 루프 안에 있는 연산들이 복잡도가 된다.

    • n이 커질수록 루프가 반복되는 횟수가 늘어난다.

    • 중첩 루프가 있다면 n * n 즉 n²이 된다.

 

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

console.time();
accumulateValues(1000000000);
console.timeEnd(); // default: 479.738ms

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

console.time();
accumulateValues(1000000000);
console.timeEnd(); //default: 0.047ms

위의 두 함수는 모두 같은 결과값을 가져오는 함수이지만 실행속도를 비교해보면 10,200배의 차이가 나는걸 확인 할수가 있다.

즉,  아래의 알고리즘이 더 효율적인 것을 확인 할수가 있는데 우

리가 어떠한 작업을 하려고 할 때 어떠한 알고리즘이 좋은것인지 모두 다 비교해보면서 하나하나 확인하기에는

시간이 오래걸릴수도, 공간을 많이 차지할수도 있는 여러가지 문제로 인해 어려울수도 있다.

또한 정확한 측정값을 확인하기가 어렵다. 기기마다, 또는 환경마다 다른 결과값이 나오기 때문이다.

이러한 문제들로 인해 하나의 척도로 사용하기 위해 시간복잡도를 사용한다.

 

시간복잡도가 필요한 이유

- 주어진 입력 크기 n에 대해 알고리즘이 수행하는 기본 연산의 수를 나타내기 때문에 알고리즘의 효율성을 평가하는 데        중요한 기준이 된다.

- 시간 복잡도가 낮을수록 알고리즘이 더 효율적이며, 큰 입력에 대해서도 더 빠르게 실행될 가능성이 높다.

- 화면이 전환되는데 O(n²)의 시간 복잡도를 가지고 9초가 걸린다고 했을때 O(n)의 시간 복잡도를 가지는 알고리즘으로 개    선한다면 3초가 걸리게 될것이기 때문이다.

- 두 개 이상의 알고리즘을 비교할 때 시간 복잡도를 사용하면, 각 알고리즘이 서로 다른 입력 크기에서 어떻게 성능이          변하는지 예측할 수 있다.

 

시간 복잡도를 그래프로 나타냈을때는 O(1) → O(logn) → O(n) → O(n²)순으로 입력의 크기가 커질수록 시간의 차이가 커진다.

다음과 같은 시간이 걸린다.

 

 

// 3중 for문
for(let i = 0 ; i < 10; i++){
	for(let j = 0; j <  n; j++){
		for(let k = 0; k < n; k++){
			if(true) console.log('안녕')
		}
	}
}

// 일반 for문
for(let i = 0; i < n; i++){
	if(true) console.log('하세요')
}

이 코드의 시간 복잡도는 3중 for문은 모든 반복을 할 시 10n²번 반복한다.

일반 for문은 모든 반복을 할 시 n번 반복한다.

10n²+n만큼의 시간이 필요하다.

가장 영향을 많이 끼치는 항(10n²)의 상수인자(10)을 뺴고 나머지항(n)을 없애면 빅오표기법이다.

즉, 빅오 표기법으로 표현하면 O(n²)이된다.

 

왜 다른항은 계산을 안할까?

증가속도를 고려한다면 증가 폭이 미미하기 때문이다.

위 그래프를 자세하게 들어가보면 일직선이아니라 다 다른점들로 연결이 되어있을것이다.

하지만 그것을 멀리서 확인 했을 때 위 그래프와 같이 보이게 되는 것이다.

또한, 입력의 크기가 커질수록 연산량이 가장 많이 커지는것은 n의 제곱항이기때문이다.

 

공간 복잡도란?

- 프로그램을 실행시켰을 떄 필요로 하는 자원 공간의 양

- 알고리즘이 문제를 해결할 때 필요로 하는 컴퓨터의 메모리 공간

- 정적변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할경우도 포함한다.

- 자원이 제한된 시스템에서 동작하는 프로그램을 구현하는 것과 같이 특별한 경우에 사용하는 분석 방법

let a = new Array(1000);

// 만약에 해당 배열이 전부 int로 채워진다면 공간복잡도는 4000바이트