Computer Science/Data Structure 썸네일형 리스트형 Heap, PQ 1. heap binaray tree의 일종으로 complete binary tree 이다. binary tree : each paren node can has 1 or 2 children node complet binary tree : except the bottom, every level if full of nodes heap order : internal node's key >= parent key (min heap_) min-heap, max-heap 이 있고 root에 min, max를 항상 둔다 따라서 min is O(1) add, remove 를 위해 last node를 추적한다. How to update the "last" node? : starting from the last node, .. 더보기 Binary Search (이분탐색) 1. 알고리즘 탐색시간은 O(logN)이다. 정렬 알고리즘은 다음과 같다. left = 0 rigth = n - 1 while left < right: mid = (left + right) / 2 if arr[mid] < target: left = mid + 1 else: right = mid if(left == right) and (arr[left] == x): found = True foundpos = left else: found = False 더보기 Map and Hash 1. Map(Hash Table) A map models a searchable collection of (key, value) entries value 중복은 허용되지만 key의 중복은 허용되지 않는다. 예시로 python의 dictionary가 있다. 2. Map ADT(abstract data type) M[k] : return the value of v associated with key k, or(if the key is not exist) raise a KeyError M[k] = v : add or replace del M[k] len(M) iter(M) k in M : return Ture if the map contains an item with key k M.get(k, d=None) .. 더보기 Amortized Analysis(분할 상환 분석) 1. 분할 상환 분석 알고리즘 분석시 각각의 연산마다 최악의 경우를 가정하는 것은 불합리하다. 어떠한 임의의 알고리즘에서 어떤 연산은 자원적 측면에서 상당한 비용을 소모하는 반면 다른 연산은 그렇게 고비용을 지불하지 않을 수도 있 상환 분석은 알고리즘의 전반적인 연산 집합에 대해 비용이 높은 연산, 그리고 비용이 덜한 연산 모두를 함께 고려한다. 2. Array Doubling : Array에 새로운 원소를 append 할 때는 O(1)의 시간이 들지만 Array가 full이 되는 순간 Array Doubling에 O(n)의 시간을 소요한 뒤에 append를 수행하게 된다. 따라서 Amortized Analysis를 통해 분석을 하고 O(1*)(amortized O(1) time) 3. Amortized.. 더보기 asymptotic notation(점근 표기법) 1. asymptotic notation : 알고리즘의 효율성을 표기위한 방법으로 상수 계수와 중요하지 않은 항목들을 제거한 것이다. 2. growth rate : n 값이 일정하게 증가함에 따라 늘어나는 시간을 확인한다. : c < logn < n < nlogn < n^2 더보기 이전 1 다음
