Data structure, Algorithm 검색 결과

해당 글 2건

시간 복잡도(Big-O) 계산하기, Worst Accepted Algorithm

왜 Big-O 표기법으로 시간 복잡도를 계산하지? Big-O 표기법은 최대 차항만 계수 없이 표기하면 되기 때문에 사용하기 간편하고, 알고리즘의 최악의 경우를 의미해서 평균과 가까운 결과를 예측 할 수 있기 때문입니다. 그래서 Big-O 복잡도가 무엇이 있는가 node.js는 (싱글 스레드인 이벤트 루프에서 기본적인 코드를 처리하므로) 싱글 스레드죠? 그렇기에 복잡도가 높은 코드를 처리하면서 blocking되는 현상을 막아야 합니다. 때문에 코드를 비동기적으로 짜야 하는 것이죠. 그런데 웹 개발을 하다보면 솔직히 O(n) 정도의 복잡도 이상의 코드를 보기가 힘듭니다. (제가 허접해서 그런 걸 수도 있습니다.) js 개발자는 이중 map, filter를 돌려 O(n^2)의 복잡도를 가진 코드를 작성하게 될..
Data structure, Algorithm/Algorithm 2021. 1. 26. 22:52

이진 트리와 B-Tree

이진 트리 Binary Tree 트리란 탐색을 위한 자료구조로, Node와 Edge로 구분되며 (그래프 이론에서 쓰던 그 용어들의 의미와 동일) 그래프와 다른 점은, 위계가 존재하기 때문에 depth가 존재한다는 것이다. 여기서 뿌리 노드의 depth를 0이라 보는 곳도 있고 1이라고 보는 곳도 있다. 여기서 자식 노드의 갯수를 차수라고 한다. A 노드의 차수는 2, C 노드의 차수는 3이다. 이 중 자식 노드가 최대 2개인 노드들로 구성된 트리를 '이진 트리'라고 부른다. 따라서 다음과 같은 특징을 가진다. 이진트리의 레벨 i에서 가질 수 있는 최대 노드의 수는 2^i이다. (i>=0) 깊이가 k인 이진트리가 가질 수 있는 최대 노드의 수는 2^k-1이다.(k>=1) 하나의 노드가 가질 수 있는 키는 ..
Data structure, Algorithm/Algorithm 2020. 10. 9. 23:15