O(1) //constant //Array LookUp, Hash Table Insertion
O(log n) //logarithmic //Binasry Search
O(n) //linear //Linked list
O(n^2) //quadratic //Constant Time Operation Inside Two Nested For-Loops
O(c^n) //exponential //Guessing An N-Character Long Password//Recursion//메모리제이션을 쓰지 않은 피보나치 수열
Arrays
Insert : O(n)
Lookup(position : O(1)
Assign : O(1)
Remove : O(n)
Find(value) : O(n)
Linked Lists
Lookup : O(n)
Find : O(n)
Assign : O(n)
Insert : O(n) (추가하고자하는 위치를 찾아야하기 때문에 O(n)이다. head에 추가하려면 O(1)이 맞지만...)
Remove : head: O(1), middle: O(n)(지우고 싶은 위치의 이전 위치를 알 수 없기 때문에 O(n))
Remove : Doubly-Linked Lists O(1)(지우고 싶은 위치의 이전 위치를 알 수 있기 때문에)
Trees
Find : O(n)
Binary Search Tree
Find : O(log n) (최악은 O(n)(tree지만 linked list와 같은 모양인 경우))
최악의 경우를 방지하기위해 좌,우의 depth를 확인하고 차이가 2이상 난다면 비틀어준다.
추가할때마다 밸런스를 확인하고 비틀어주고 반복
BST가 sorted array(정렬된 배열)보다 좋은 이유:
array는 연속된 메모리 공간을 차지하지만 Tree형식은 비연속적인 데이터들을 연결해주기 때문에 더 효율적이다.
Big-O
최악의 경우
Big-Omega
최선의 경우
Big theta
평균적인 경우 //오메가 세타 반대??? 다시 찾아보기
오메가, 세타는 잘 안쓰임 왜냐면 항상 최악을 가정해야하기 때문(만에 하나 문제가 생기면 안되니까)
소크라티브
O(1)
O(log n)
O(n) => 빠른 알고리즘
O(n*log n)
O(n^2) => 500만~1000만
O(n^3) => 입력값이 적을 때
O(n!)
무조건적으로 Big-O값에 의존하지 말고 입력값을 고려해서 종합적으로 생각하자!!
Big-O에서 계수는 무시한다.
e.g. 2n => O(n)
parseInt(x) //x의 정수부분만(소수부는 버림)
i++ //i+=1 //i=i+1
i=k : ik...k
각 데이터 구조의 실생활 예제 찾아보기
