👩💻Developer/Data Structure and Algorithms8 AVL tree란 무엇인가? * 해당 글은 학과 수업으로 배운 내용과 코드가 포함되어 있으며 개인적 공부 목적으로 업로드하였습니다. 우리는 이전에 bst dictionary에서 lookup, insert 그리고 find_min이 O(log n)의 cost를 가진다는 걸 확인했었다. 하지만 모든 종류의 BST에서 전부 O(log n)cost를 가질까? empty BST에 아래와 같은 insertions을 진행한다고 해보자 insert 10 insert 20 insert 30 insert 40 insert 50 insert 60 60까지 넣고 나면 아래와 같이 tree가 형성된다. 이 tree에서 70을 lookup 하려면 모든 node를 체크해야하기에 O(n)의 cost가 필요하다. 이를 통해 우리는 O(log n) 이 항상 보장되지.. 2022. 11. 14. Binary Search Trees란 무엇인가? * 해당 글은 학과 수업으로 배운 내용과 코드가 포함되어 있으며 개인적 공부 목적으로 업로드하였습니다. n entries를 가진 다양한 dictionaries들의 시간 복잡도를 우리는 아래와 같이 정리할 수 있다. Unsorted Array Array sorted by key Linked list Hash Table lookup O(n) O(logn) O(n) O(1) insert O(1) O(n) O(1) O(1) 위 표를 살펴보면 우리는 hash dictionary가 가장 efficient하게 보인다. -Average: O(1) -Amortized: O(1) 하지만 가장 작은 key를 가진 entry를 찾는 것 등의 operation은 O(n)의 cost가 필요하다 이버 공부에 우리의 목적은 look.. 2022. 11. 14. Function Pointer란 무엇인가? * 해당 글은 학과 수업으로 배운 내용과 코드가 포함되어 있으며 개인적 공부 목적으로 업로드하였습니다. 우리는 앞서 C0 memory model에서 두가지의 memory를 살펴보았다. -Local memories 와 allocated memories 하지만 실제 컴퓨터에는 하나의 memory만 존재한다. 따라서 local 과 allocated memory는 이 큰 하나의 memory에 두가지 segments일 뿐이다. Allocated memory가 있는 segment를 우리는 heap이라고 부른다. local memory가 있는 segment를 우리는 stack이라고 부른다. -function call에 따라 이 stack은 커지기도, 작아지기도 한다. stack은 점점 커지고 heap이 점점 커져서 .. 2022. 11. 13. Hash Dictionary란 무엇인가? * 해당 글은 학과 수업으로 배운 내용과 코드가 포함되어 있으며 개인적 공부 목적으로 업로드하였습니다. 우리는 이전에 hash dictionary library를 살펴본 적이 있다. 이 library는 generic한가? -Generic Libraries란 1) client가 data type을 선택할 수 있어야 하고 2) 같은 application안에서 다른 data type에 따라 multiple instances 가 가능해야 한다. Hash Dictionary를 살펴보면 // typedef ___ * entry; // typedef ___ key; 를 통해 우리는 client가 data type을 선택할 수 있음을 확인할 수 있다. 그러나 같은 application안에서 multiple instan.. 2022. 11. 13. 이전 1 2 다음
