Big-O notation

Jveloper 2019. 5. 7. 13:59

* 시간복잡도와 공간복잡도 // 여기서는 시간복잡도에 대해서만 정리를 한다

- 큰 프로그램일수록 효율적으로 코드(알고리즘)를 짜야함
- 머신러닝, 데이터분석 등등 좋은성능의 좋은 알고리즘을 필요로함

O(1)

- 상수시간 즉, 한번만 연산하면 바로 답이 나온다는 소리

- example : Array lookup(indexof), HashTable Insertion(종류중 하나 : 객체 key,valuer값 찾는것이 있음)

- lookup이란? array의 index를 가지고 특정 element를 찾아내는것

- Hashtable이란? object가 해쉬테이블의 하나의 형태라고 볼 수 있음

- Hashtable insertion? 특정키로 새로운 value를 추가, 또는 가져오고 삭제하는것

O(log n)

- example : 바이너리 서치(binary search)

- 나누고 정복을 반복( divide and conquer )

- 탐색 알고리즘 중 하나

O(n)

- O(2n) 도 O(n)이다 -> 이유: 근사치로 판단하기 때문

- example : for문 (array.length만큼 도는.)

-----------------------------------------------------> O(n log n) - example : Quick sort, Merge sort, Heap sort

O(n²)

- example : 2중 for문

O(cⁿ)

- 거의 버그에 가까움

- example : password를 만들때

- 패스워드가 길면 길수록 뚫기가 어렵기 때문

당연한 소리겠지만 , 런타임속도는 위로 올라갈수록 좋다

* complexity cheat sheet 검색하면 어떤때에 어떤걸쓰면 최악의 상황을 피할수 있는지 알 수 있음