TIL 2020.12.08

RECURSION

Function recursive(...parameters){
// base case
if(더이상 쪼개지지 않는 상태){
return
}

Big O notation

  • Big O (O): 최악의 경우
  • Big Omega (Ω) : 최상의 경우
  • Big Theta (Ө): 최악과 최상의 중간
  • DROP CONSTANTS!

constant: array look up, hash table insertion

logarithmic: binary search tree

linear: for loop(up to n)

quadric: constant time operation inside two nested for-loops

exponential: recursion(fibonacci)

  • O(logn)이 O(n)보다 항상 빠르지는 않음. n=1일 때 예외

Array

  • Lookup(position): O(1)
  • Assign: O(1)
  • Insert: O(n)
  • Remove: O(n)
  • Find(value): O(n)

Singly Linked List

  • Lookup: O(n)
  • Assign: O(n)
  • Insert: O(1)어디에 넣을건지 알면 // 모르면 O(n)
  • Remove: head-O(1) middle-O(n)
  • Find(value): O(n)

Doubly Linked List

  • Lookup: O(n)
  • Assign: O(n)
  • Insert: O(1)
  • Remove: O(1)
  • Find(value): O(n)

Binary Search Tree

  • As above, it is unbalanced, which means depth is more than 1 between parent and both children
  • in order to be balanced, it is better to re-balance as node inserted
  • better to user BST over sorted array because trees occupy non-contiguous memory

reference:

Consistency achieves everything https://github.com/paigekim29