IM 1W _ 시간복잡도와 자료구조 정리

시간복잡도

• 중요한 이유?

• 알고리즘의 시간 복잡도를 나타낼 수 있는 표기법들
  big O notation = 최악의 경우를 다루는 표기법
  big Omega notation = 최선의 경우를 다루는 표기법 // 거의 쓸 일이 없음
  big theta notation = 최악과 최선의 절반 지점의 경우를 다루는 표기법 // 역시 쓸 일이 없음

---

ex)
arr = [100, 102, 105, 1111, 1112, 34124, ..., 1231231, 11111111]에서 55555찾기

arr[parseInt(arr.length/2)] < 55555

2^3 ===
log2(아래)8(위) = 3 (2를 몇번잘라야 8이 없어집니까)???

10000
log3
3333
1111
111
33
11
3
1

->입력값이 작으면, 별로 차이가 안남
->입력값이 크면,...?

---

쓰임새

• 스택 : 프로그래밍 언어의 런타임에서 함수의 호출을 관리, undo, 재생목록관리
• 큐 : 메시지 큐, 메시지 브로커, node.js런타임에서 이벤트 큐, BFS(너비우선탐색)
• 링드리스트 : 파일시스템에서 많이 쓰임.. / 자료의 추가와 삭제가 빈번히 일어날 경우 /
• 해시테이블 : 딕셔너리(객체), Map, 해시함수는 정말 많이 ㅆ임, p2p시스템에서 노드 주소관리, 로드밸런싱
• 트리 : 진짜 많이 씀 / 자료 빨리 쓰고 싶을 때 / 넣을 때는 힘들지만.. / binary search tree / 2-3-4 tree, b-tree, radix tree(자동완성검색), patricia tree (우선순위는 앞쪽부터)
• 그래프 : 네비게이션, sns, 싸이월드 (무방향성 모두1촌), 인스타(양방향성), 몇번만에 도달할 수 있느냐가 촌수라고 생각하면 됨 /

-> 구현전까지
-> 굵은글씨는 구현까지

알고리즘문제를 찾아나서기
스택>>
let actions = ["paint, "erase", "make a line"]
시나리오1. 페인트를 하고,지우고, 선을 그리고, 다시 페인트를 하고, 다시 선ㅇ르 그리고, 선을 한번 더 그렸다 / user가 undo를 2번 하고 지우기를 했다. / 이때 스택의 모습은?

큐>>
예매사이트 / bts콘서트 / 여러 사이트 구매버튼을 눌렀다 / 분식집 주문을 받았다 /

let Q = [];
const enQ = item => Q.push(item)
const dQ = () => {
const head = Q[0];
Q = Q.slice(1);
return head;
}
이런식으로 예제 구현해보기

arr.forEach(callback)
과 같은
_ .each(arr.callback)
선호하는 것으로 쓰기

---

나중에 보기.. ㅎ

배민 기술블로그
네이버 기술블로그
linkedin 기술블로그
8 bitmen