알고리즘 & 자료구조 스터디 1주차 [Big O]

☺︎ big O 를 사용하는 이유?

• 코드를 분류하는 시스템(목적)
• BigO 는 좋은 코드,, 나쁜 코드라고 말하는 것들을 숫자와 문자로 성능을 표기
• 지진 리히터 척도
  • "지진이 얼마나 심해??"
  • "강도 7.9...!!!"
  • "강도 3.1~"

☺︎ 코드 시간 재기

• “ 1~10 까지의 합을 구하라”
  • A . 1~10 까지 반복문을 통해 더하기
  • function addUpTo (n) { let total = 0; for (let i =1; i<= n; i++) { total += i; } return total; }
  • B . 수학 공식을 사용하여 구하기
  • function addUpTo(n){ return n * ( n + 1 ) / 2; }
• 시간 측정도
  • A 의 시간
    
    
  • B 의 시간
    
• let t1 = performance.now(); addUpTo(100000000); let t2 = performance.now(); console.log(`Time Elapsed: ${(t2 - t1) / 1000 } seconds. `)

• 값이 작을 때는 크게 차이가 없어 보이지만 값이 커지면 커질수록 변화가 생김!
• 계속 이런식으로 측정을 한다면 컴퓨터, 사용하는 프로그램에 따라 결과값이 달라지는 어떻게 할까? => BigO

☺︎ 본격적으로 BigO (얼마나 빠른가?)

• BigO : 입력된 내용이 늘어날수록 알고리즘에 실행시간이 어떻게 변하는지 설명하는 공식적인 방식! ⇒ 입력의 크기와 실행시간의 관계
• A,B,C를 봤을 때 n의 값이 커질 때 실행시간과 과정을 살펴보면서 이해

• BigO를 이해하기 위한 예시들 ⇒ 살펴볼 때 실행시간과 가정을 이해해보자😎
• //ex)1 function logAtLeast5(n){ // n의 값이 커지면 커질수록 max의 값이 바뀜...! for(var i = 1; i<=Math.max(5,n);i++){ console.log(i); } } // O(n)의 실행시간 //ex)2 function logAtMost5(n){ // n의 값이 커지면 커질수록 min의 값에는 변화는 없다. // n의 값이 영향을 주지 않는다!! for(var i = 1; i<=Math.min(5,n);i++){ console.log(i); } } // O(1)의 실행시간
• BigO의 전반적인 추세 그래프 ( 여기서.. log(n))이 밑이 2인걸 처음알게됨..)

☺︎ 공간 복잡도 ( 얼마나 많은 공간을 차지할까?? 🤔)

• Rules of Thumb

• O(1), O(n)에 대한 이해(값이 아닌 공간이 얼마나 차지하는지에 접근하자.)
  • O(1) : a에 1001이라는 값 한개.

• O(n) : a~n 까지의 알파벳의 공간

☺︎ Big O of Objects (later 해쉬테이블, 맵..!)

let user = {
    name: 'seunghyun',
  isAdult: false,
  favorite: ['soccer','cook']
};

• insertion - O(1) ex) “싫어하는 것을 추가하자. ⇒ hate : [’coding’, ‘study’] “
• Removal - O(1) ex) isAdult 제거
• Searching - O(N) ex) “가장 좋아하는 것을 찾아라!” → name 지나고,,, isAdult 지나고,,,, favorite”
• Access - O(1)

☺︎ Big O of Objects Methods

• Object.keys - O(N)
• Object.values - O(N)
• Object.entries - O(N)
• hasWonProperty - O(1)

⇒ keys,values,entries의 경우에는 객체에 접근해서 배열을 반환하기 때문에 아이템 개수가 늘어나면 배열에 추가해야하는 시간이 늘기 때문에 O(N)

⇒ hasOwnProperty 는 user.hasOwnProperty(’name’) 을 입력하면 name이라는 속성이 있는지 없는지 boolean으로 알려주기 때문에 O(1)

☺︎ Big O of Arrays

const ex = ['a', 'b', 'c']

• insertion - it depends…
  • index 라는 존재 때문에! → 새로운 값을 앞에 추가하게 되면 기존 인덱스의 값들이 변한다.
• Removal - it depends…
  • insertion과 같은 원리
• Searching - O(N)
  • 반복문을 써서 처음값부터 원하는 N까지 순회를 해야한다. → 값이 커질수록 시간이 길어지기 때문에 O(n)
• Access - O(1)

☺︎ Big O of Arrays Operations

• push - O(1)
• pop - O(1)
• shift - O(N)
• unshift - O(N)
• concat - O(N)
  • 배열을 합쳐주는 과정 → 다른 배열의 크기가 크면 클수록 시간이 증가
• slice - O(N)
  • 배열의 일부를 가져오거나 전체를 가져온다. → element 의 갯수만큼 걸리는 시간이 소요
• splice - O(N)
  • slice와 달리 element 를 제거하고 추가한다.
• sort - O(N*log N)
  • 배열을 정렬하는 것은 다양한 방법이 있지만 element를 이동해서 정렬하기 위해서는 복잡
• forEach,map,filter,reduce,etc… - O(N)

☺︎ 느낀점

• 과거에 BigO 에 대해 배웠을 때에는 반복문... o(n) 2중for문 .. o(n제곱).. 이런식으로 암기만 했었는데 기초부터 다시 정리를 하니 이제야 왜 교수님이 무슨말을 했었던 것인지 이해가 된다.
• 그 당시에 교수님이 못가르친다고 드랍했었는데 내가 못받아드렸다는 것을 느끼면서.. 겸손하게.. 열심히 해야겠다.

스터디 자료: https://www.udemy.com/