자료구조와 알고리즘, 시간복잡도/공간복잡도 (Big O)

Big-O란?

알고리즘의 효율성을 표기해주는 표기법

 

시간 복잡도: 알고리즘의 시간 효율성
공간 복잡도: 알고리즘의 공간(메모리) 효율성

 

1. O(1) : 스택에서 Push, Pop

2. O(log n) : 이진트리

3. O(n) : for 문

4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)

5. O(n²): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)

6. O(2ⁿ) : 피보나치 수열

 

참고:

https://noahlogs.tistory.com/27

빅오 표기법 (big-O notation) 이란

https://soldonii.tistory.com/56https://soldonii.tistory.com/56

자바스크립트에서 Big O(시간 복잡도)란?