[알고리즘] Big O표기법

🍕Big O?

-빅오는 대략적으로 숫자를 세는 것에 붙인 공식적인 표현이다.

-it allows us to talk formally about how the runtime of an algorithm grows as the input grow

(정식으로 입력된 내용이 늘어날수록 알고리즘에 실행 시간이 어떻게 변하는 지 설명하는 공식적인 방식)

-> 어떤 function 함수의 입력값이 늘어나는 것과 입력의 크기와 실행시간의 관계를 말한다. 

[정의]  Big-O notation은 알고리즘의 시간 복잡도를 나타내는 표기법이며, O(f(n))으로 나타낸다. 

 

🍕왜 big O표기법을 사용할까? 

명령어의 실행시간은 컴퓨터의 하드웨어 또는 프로그래밍 언어에 따라 편차가 크게 달라지기 때문에 명령어의 실행 횟수만을 고려하는 것, 그래서 시간 복잡도를 나타내는 big O표기법을 사용하는 것이다. 

 

🍕알고리즘의 시간 복잡도 

알고리즘의 복잡도를 판단하는 척도로는 시간 복잡도와 공간 복잡도 두 가지가 있는데, Big O표기법은 시간 복잡도를 다룬다. 

• 시간복잡도(time complexity): 입력된 n의 크기에 따라 실행되는 조작(연산)의 수

알고리즘은 연산이 많아질수록 속도가 오래 걸린다. 따라서 시간 복잡도는 알고리즘 내 연산의 횟수와 관계있다. 

 

input = runtime 

• f(n) could be linear (f(n) = n) // 선형, 즉 N의 값이 커질수록 실행 시간도 같이 늘어난다. 
• f(n) could be quadratic (f(n) = n^2) // n제곱 표현한거, 실행시간이 n의 제곱일수도 있다. 
• f(n) could be constant (f(n)=1) // 실행시간이 상수일수도 있다. -> n이 커져도 실행시간에는 아무 영향도 받지 않기 때문에 항상 상수이다. 이것을 단순하게 1이라고 표현한다. 
• f(n) could be something entirely different

※Big -O 표기는 복잡한 함수 f(n)이 있을 경우 이 함수의 실행 상한과 하한을 의미한다. 

즉, 가장 빨리 실행될 때가 하한, 늦게 실행될 때가 상한을 뜻한다. 

가장 늦게 실행될 때를 빅오(O), 가장 빨리-> 빅 오메가(Ω), 평균 -> 빅세타(θ)로 지칭한다.

n이 작을때, 즉 n0이하 일때의 값이 작은 경우는 무시하며 빅오 표기법은 n이 매우 클 때의 전체적인 그림에 집중한다.

-> 빅오 표기법은 주어진(최선/평균/최악) 경우의 수행 시간의 상한을 나타낸다.

-> 알고리즘 효율성을 상한선 기준으로 표기하기 때문( 알고리즘 효율성은 값이 클수록 즉, 그래프가 위로 향할수록 비효율적임을 의미)

🍕빅오 표현식 단순화하기 

1. constants don't matter ->  상수는 무시한다. 

2. smaller terms don't matter  ->  작은 연산 무시됨

 

▶Big O Shorthands

1. Arithmetic operations are constant // 산수는 상수입니다. 덧셈 뺄셈 곱셈 나눗셈 포함, n의 값에 상관이없음

2. Variable assignment is constant // 변수할당하는 것도 상수임 

3. Accessing element in an array( by index) or object ( by key) is constant // 배열에 인덱스로 요소에 접근하는거나 객체에 키로 접근하는것은 상수이다. 

4. In a loop, the loop times the complexity of whatever happens inside of the loop 

->  복잡도(complexity) = 루프의 길이  x(곱하기) 루프 안에 있는 연산들

 

▶시간복잡도에서 중요하게 보는 것은 가장 큰 영향을 미치는 n의 단위

- 상수항은 무시, 영향력 없는 항은 무시 

예시

1	O(1)	상수
2n + 20	O(n)	n이 가장 큰 영향을 미친다.
3n^2	O(n^2)	n^2 이 가장 큰 영향을 미친다.

▶시간 복잡도의 문제해결 단계 

O(1)	상수 시간	문제를 해결하는데 오직 한 단계만 처리함.
O(log n)	로그 시간(logarithmic time)	문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬
O(n)	직선적 시간(linear time)	문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐
O(n log n)	linearithmic time	문제를 해결하기 위한 단계의 수가 n*(log2n)번 만큼의 수행시간을 가진다. 로그 선형 알고리즘
O(n^2)	2차 시간(Quadratic time)	문제를 해결하기 위한 단계의 수는 입력값 n의 제곱
O(C^n)	지수 시간(Expontential time)	문제를 해결하기 위한 단계의 수는 주어진 상수값 C의 제곱

 

🍕빅오 표기법 성능비교 

O(1) : 입력값(n)에 상관없이 일정한 실행시간을 가지는 최고의 알고리즘이라고 할 수 있다. 하지만 상수 시간에 실행된다해도 상수값이 상상 이상으로 클 경우 사실상 일정한 시간의 의미가 없다. 

O(log n) : 로그는 매우 큰 입력값에서도 크게 영향을 받지 않는 편이다. 매우 견고한 알고리즘으로 이진 탐색의 경우가 이에 해당한다. 

O(n) : 알고리즘을 수행하는데 걸리는 시간이 입력값에 비례한다. 이러한 알고리즘을 선형 알고리즘이라 부른다.

정렬되지 않은 리스트에서 최대 또는 최솟값을 찾는 경우에 해당되며 모든 입력값을 적어도 한 번 이상은 살펴봐야 한다. 

O(n log n) : 병합 정렬등의 대부분 효율이 좋은 알고리즘이 이에 해당한다. 아무리 좋은 알고리즘이라도 n log n 보다 빠를 수 없다. 입력값이 최선일 경우, 비교를 건너 뛰어 O(n)이 될 수 있다. + 선형(linear)알고리즘보다 약간 느리다. 

O(2^n): 피보나치의 수를 재귀로 계산하는 알고리즘이 이에 해당 n^2 와 혼동되는 경우가 있는데 2^n이 훨씬 크다.

O(n!): 가장 느린 알고리즘으로 입력값이 조금만 커져도 계산이 어렵다.  

 

▶시간 복잡도 성능 비교

(왼 ->오 순으로 효율성이 떨어짐, 즉 왼쪽이 가장 빠름) 

 

상수함수 < 로그함수 < 선형함수< 다항함수< 지수함수

 

---

O(1) 

예시 코드

function addUpTo(n){
    return n * (n + 1) / 2; 
}
//console.log(addUpTo(6)); output :21 

//Add1 과 같은 결과가 나온다. 
//What does better mean? 

//성능 체크 코드 
//브라우저 API performance.now()사용

const time1 = performance.now();
addUpTo(1000000000);
const time2 = performance.now();
console.log(`Time Elapsed : ${time2 - time1 / 1000}seconds.`);

- always 3 operations (연산자가 3개밖에 없으니까 input인 n에 상관없이 3번만 연산만 한다.)

-> 그래서 O(1) 라고 표현합니다. 

 

O(n)

예시 코드

function addUpTo(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}
//console.log(addUpTo(6));

const time1 = performance.now();
addUpTo(1000000000);
const time2 = performance.now();
console.log(`Time Elapsed : ${time2 - time1 / 1000}seconds.`);

-Number of operations is (eventually) bounded by a multiple of n (say, 10n)

( 연산 횟수는 결국 n의 배수로 제한된다. ) 

-> 그래서 O(n)으로 표시됨 

 

 

다음 빅오 표현식을 간단히 해보자

빅오 표현식: O(n^2 + n^3)

A. O(n^3)

 

아래 함수에 대한 시간 복잡도를 구하세요. 

function logUpTo(n){
for(let i=1; i <= n; i++){
console.log(i);
	}
}

A. O(n)

 

---

🍕알고리즘의 공간 복잡도 

-입력이 커질수록 알고리즘이 얼마나 많은 공간을 차지하는지에 대해서 나타낸다.

• 공간복잡도(space complexity): 알고리즘이 실행될 때 사용하는 메모리의 양 

'입력'이 무엇인가(what about the input)?

- 당연한 것은 n이 커질수록, 무한대까지 가면서 입력 자체가 커진다는 것이다.  (이 부분은 무시하고 알고리즘 공간 복잡도에 대해서 설명) 

• 보조 공간 복잡도(auxiliary space complexity): 입력되는 것을 제외하고 '알고리즘 자체가 필요로 하는 공간을 의미'

결론:   알고리즘의 공간 복잡도는 사실상 '보조 공간 복잡도'를 의미한다.  

// 기본적으로 알고리즘 내에서 일어나는 일에 집중하는 것

🍕자바스크립트의 공간 복잡도 규칙

• most primitives (booleans, numbers, undefined, null )are constant space // 불리언, 숫자, 언디파인, 널값은 자바스크립트에서 모두 불변 공간입니다. -> 입력의 크기와는 상관없이 숫자가 1이든 1000이든 모두 불변 공간이라 여김(같은 크기를 차지함)
• Strings requires O(n) space (where n is the string length) // 문자열은 다르다. 문자열은 O(n) 공간이 필요합니다. -> n이 50이고 n이 문자열의 길이라고 했을 때, 그 문자열은 길이가 1자인 문자열보다 50배 더 많은 공간을 차지하게 된다.
• reference 타입, 배열과 객체도 문자열과 마찬가지. 대부분 O(n)이라고 여겨짐 여기서 n은 배열의 길이이거나 객체의 키 갯수일 수 있습니다. 

공간 복잡도 예제

function sum(arr) {
  let total = 0; // 여기서 숫자 할당
  for (let i = 0; i < arr.length; i++) {
    total += arr[i]; // let i = 0; 숫자 할당
  }
  return total;
}
// 결론적으로 상수 공간이 있다는 것 -> O(1) 공간

//Example 2
function double(arr) {
  let newArr = []; // 참조타입(배열) 메모리 할당
  for (let i = 0; i < arr.length; i++) {
    newArr.push(2 * arr[i]);
  }
  return newArr;
}
//입력된 배열의 길이가 50이면 50개의 아이템을 담은 새로운 배열을 리턴한다. 
// 즉, 차지하는 공간은 입력된 배열의 크기와 비례해서 커지게 된다. 
// 여기서는 let newArr = [] 나 let i = 0과 같은 것은 크게 의미가 없다. 
// O(n)로 단순화 할 수 있음

 

 

🍕로그(Logariths)

로그에 대한 개념에 대해서 배워보도록 하자

- big O 표기법에서 복잡한 수학적 표현이 있을 때를 대비해서 알아두는 것이 좋음

• 짧게 말하면 로그함수는 지수함수의 역함이다. (나눗셈과 곱셈이 짝인 것처럼 로그함수와 지수함수는 짝임)

eng, kor versions

로그함수는 항상 '2' 를 밑으로 가지지 않습니다. 하지만 가장 흔한 것은 log 2라고 쓰는 이진 로그 입니다. 

2의 몇승이..? 로 시작하는 질문을 묻는 것 앞과 마찬가지로 10진로그(base가 10인 것)도 있음 10의 몇 승이? .. 라는 질문을 묻는 것

 

->빅오 표기법에서 쓰여지는 log들은 밑이 생략되어서 표현됨 

 

왜 로그를 신경써야 하는가?

• 특정한 탐색 알고리즘들이 로그 시간 복잡도를 가지고 있음
• 모든 정렬 알고리즘이 그런 것은 아니지만 효율적인 것들이 그렇다. // O(log n)이 두번째로 좋은 시간복잡도를 가지고 있는 것을 보면 알 수 있음
• 차후에 나오는 재귀(recursion)가 때때로 로그 공간복잡도를 포함하고 있음( Recursion sometimes involves logarithmic space complexity.)

->탐색 알고리즘(시간 복잡도), 효율적인 정렬 알고리즘, 재귀(공간 복잡도) 에서 로그개념이 나오니까 알아둬야 한다. 

 

---

🍕총평

• 알고리즘의 성능을 분석하기 위해서 빅오표기법(Big O Notation)을 쓴다.
• 빅오를 통해서 시간과 공간 복잡도에 대한 이해를 높일 수 있다.
• 정확도가 아니라 전체적인 추세에 집중한다.
• 빅오로 측정되는 알고리즘의 시간과 공간 복잡도는 하드웨어에 영향을 받지 않는다.