Big O?

여러 문제 해결 방법 중 무엇이 가장 좋은 지 알 수 있다. 코드의 일반화를 통해 분류된 이름을 붙힌다.

Big O Notation?

애매한 측량을 정형화한 방법. 알고리즘에 입력값이 커짐에 따라 실행시간이 늘어나는 정도의 관계. 추세에만 신경쓰는 것! (세세한 부분은 넘어간다.)

• N이 증가함에 따라 컴퓨터가 수행해야하는 단순 동작의 수가 상수로 수렴하는 f(n)보다 작은 값이 된다면 알고리즘이 O(n)이라고 부른다.
  f(n) = n // 직선
  f(n) = n^2 // 2차함수
  f(n)= 1 // 일정한 값

ex) 1부터 n까지의 합을 만드는 함수
1. O(n) operations의 개수가 n의 배수와 관련이 있다.

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

2.O(1) 항상 3개의 operations

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

ex) 또 다른 예시

function countUpAndDown(n){
	console.log('Going Up!");
    for(let i =0; i<n; i++){
    	console.log(i);}
    console.log('At the top! Going down...');
    for(let j = n -1; j >=0; j--){
    	console.log(j);
    console.log('Back down. Bye!');}}

O(n)이 몇 개이든 trend가 중요하기 때문에 그냥 O(n)이다.

ex) 또 다른 예시 - O(n^2)

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

시간 복잡도 Big O 표기법 단순화 하기

눈대중 규칙

1. 상수는 신경쓰지 않는다.

O(2n) ❌ O(n) ⭕️
O(500) ❌ O(1) ⭕️
O(13n^2) ❌ O(n^2) ⭕️

2. 더 작은 단위는 신경쓰지 않는다.

O(n + 10) ❌ O(n) ⭕️
O(100n + 50) ❌ O(n) ⭕️
O(n^2 + 2n) ❌ O(n^2) ⭕️

ex) O(n)

logALeast5(n){
	for(let i = 1; i<=Math.Max(5,n); i++){
    	console.log(i);
        }
       }

ex) O(1) - 5 아래의 숫자만 신경쓰면 되므로 n은 상관이 없다.

logAMost5(n){
	for(let i = 1; i<=Math.Min(5,n); i++){
    	console.log(i);
        }
       }

공간복잡도

눈대중 규칙

1. 대부분의 primitives(booleans, numbers, undefined, null) are constant space.

2. strings는 O(n)space이다. (n은 string의 길이를 뜻한다.

3. Reference type(객체와 같은) 은 O(n) space 이다. (n은 배열의 길이 객체에서는 key의 갯수를 말한다.)

ex) O(1) Space - n이 상관없다.

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

ex) O(n) Space - arr의 길이가 중요하다.

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

로그와 색션 재생

logarithms => 지수를 반대로 한 것
log2(8) = 3
log2(value) = exponent => 2^exponent = value