Big O notation & Array

Complexity Analysis

: Programmer은 아래 2가지를 고민한다

How much time does this algorithm need to finish?

How much space does this algorithm need to finish?

 

Big-O Notation

Big-O Notation gives an upper bound of the complexity in the worst case, helping to quantify performance as the input size becomes arbitrarily large

n : input 사이즈

Constant Time	O(1)
Logarithmic Time	O(log(n))
Linear Time	O(n)
Linearithmic Time	O(nlog(n))
Quadric Time	O(n**2)
Cubic Time	O(n**3)
Exponential Time	O(b**n)  (b>1)
Factorial Time	O(n!)

Big O는 가장 최악의 상황(input이 가장 클때)만 고려하기 때문에 

O(n+c) = O(n)

O(cn) = O(n) (c>0)

무한한 값에 더해도 빼도 무한한 Big O임

 

예제)

input을 함수 f(n)으로 정의 가능할 때,

f(n) = 7log(n)^3 + 15n^2 + 2n^3 + 8일 때 O(f(n))은 각 항 중에 최대 값인 O(n^3)에 해당함

 

부분 set를 찾을 때 : O(2^n)

문자의 순열을 찾을 때: O(n!)

Mergesort를 이용한 sorting : O(nlog(n))

n*m 행렬 순회: O(nm)

 

---

 

Static and Dynamic Arrays

Static Array란?

: Fixed length container containing n elements indexable(숫자로 참조가 가능한) from the range [0,n-1]

 

<Complexity>	Static Array	Dynamic Array
Access	O(1)	O(1)
Search	O(n)	O(n)
Insertion	N/A  (static하기 때문에 삽입 불가)	O(n)      옆으로 다 복사/밀어야함
Appending	N/A (static하기 때문에 추가 불가)	O(1)
Deletion	N/A (static하기 때문에 삭제 불가)	O(n)

 

 

 

 

(이 글은 freeCodeCamp의 Data Structures Easy to Advanced Course -Full Tutorial from google engineer을 바탕으로 정리한 내용입니다.)