[알고리즘] 빅오표기법

빅오표기법

빅오표기법는 대략적으로 숫자를 세는 것이다. 입력된 내용이 늘어날 수록 알고리즘에 실행 시간이 어떻게 변하는지 설명해주는 방식이다. 

어떤 function의 입력 값이 늘어나는 것과 function 실행 시간이 변하는 관계를 의미한다.

알고리즘의 성능 평가를 하기 위해서 사용

하드웨어의 영향을 받지 않는다. 

 

즉, 입력의 크기와 실행시간의 관계를 의미

• (f(n)=n) | n의 값이 커질수록 실행시간도 늘어난다.
• (f(n)=n*n | 실행시간이 n의 제곱일 수도 있다. 
• f(n) = 1 | n이 커져도 실행 시간에는 아무런 영향을 받지 않기에 항상 상수일 수 있다. (간단하게 표현하기 위해 1로 표시)
• f(n)이 완전이 다를 수도 있다. 

빅오 표기법의 필요성

• 여러가지 코드를 일반적으로 서로 비교하고 성능을 평가하는 방법임으로 필요하다.
• 비효율적인 코드를 찾는데 도움이 된다.

---

시간 복잡도

• 시간과 관련하여, 알고리즘이 얼마나 빠르게 실행하는지에 관한것
•  입력이 커질수록 알고리즘의 실행속도가 어떻게 바뀌는지 분석 가능

 

🤨 n이 커질수록 실행 시간이 어떻게 영향을 받나?

 

O(1)

 

오른쪽 사진의 그래프의 선변화가 없기에 1이다. (물론 예시이긴하다.) 

n의 값이 커질수록, 아무 변화가 없다. 즉, 실행 시간은 변하지 않는다.

 

O(n)

 

n이 커질수록 비례하게 실행 시간이 늘어난다.

 

 

 

 

O(n²)

 

printAllParis함수는 중첩된 for문으로 이뤄져있다.

첫번째 for문은 O(n)이다. 

두번째 for문은 O(n)일까? O(2n)일까?

 

정답은 O(n)이다. 왜일까? 중첩된 for문이기 때문이다. 

그래서 O(n)안에 O(n)이 있으므로 O(n²)이다. 

또한, 설명을 덧붙이자면, n이 커질수록 실행시간이 n ²의 값으로 늘어나기때문에 O(n²)이다. 

 

✅ 기본적으로 입력인 n이 커질수록 알고리즘이 얼마나 효율적인지 표현하는 방식

---

 

빅오 표기법 단순화

🤓 큰 그림을 생각하자! 

O(100)              → O(1)

O(n+10)            → O(n)

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

O(n² + 5n)         → O(n²)

 

✏️ 빅오 표기법을 단순화 규칙

• 산술 연산은 상수 시간이다 . (덧셈, 뺄셈, 곱셈, 나눗셈을 포함)
  • 입력의 크기에 상관없이 항상 일정한 시간 내 수행한다.
• 변수 할당은 상수 시간이다.
  
  • ex) x = 1000을 처리하는 것과 x = 2000을 하든 처리하는 것은 비슷한 시간이 걸린다. 
  • 변수를 새로 정의하거나 값을 할당하는 작업은 입력의 크기와 상관없이 일정한 시간 내에 완료된다. 
• 배열의 요소에 접근하거나 객체의 키를 통해 접근하는 것은 상수이다.
  • 배열의 특정 인덱스에 접근하거나 객체의 특정 키를 통해 값을 찾는 작업은 시간 복잡도가 입력 크기에 관계없이 일정하다. 
• 루프 내에서의 복잡도는 루프의 길이와 루프 내부에서 일어나는 작업의 복잡도의 곱이다
  • 0에서 n까지 간다면, n이 커질수록 루프가 반복되는 횟수가 늘어난다.
    • 만일 중첩루프가 있다면 n²이 실행시간이 될 수 있다.

---

공간복잡도

• 사용되는 메모리에 집중하겠다.
• n이 커질수록, 무한대까지 가면서 입력 자체가 커진다는 것을 잊지말아야한다. 
• 전체적인 추세를 중요하게 생각하자!

✏️ 빅오 표기법을 단순화 규칙

• 불, 숫자, undefined, null은 자바스크립트에서 모두 불변 공간이다.
  • 그렇기에 입력의 크기와는 상관없이, 숫자가 1이든, 100이든 모두 불변 공간 취급(불이 사실이든 거짓이든)
• 문자열은 조금 다르다. 문자열은 O(n) 공간이 필요
  • 만일 문자열이 50자라면, 그 문자열의 길이가 1자인 문자열보다 50배 더 많은 공간 차지하게 된다.
  • reference타입, 배열, 객체 또한 그렇다. 대부분 O(n)이라고 생각한다.
  • n은 배열의 길이거나 객체의 키 갯수일 수 있다.

O(1) 공간

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

 

 

O(n) 공간

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

• 차지하는 공간은 입력된 배열의 크기와 비례해서 커지게 된다.

---

O(log n)

ex) log₂(8) = 3

• 어떤 이진 로그를 대략 계산하기 위해서는 그 숫자가 1보다 작아지기 전에 2로 나눠지는 횟수이다.