Big-O notation

시간복잡도

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

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

---

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 검색하면 어떤때에 어떤걸쓰면 최악의 상황을 피할수 있는지 알 수 있음