Big-O

이글은 해당 게시글(https://noahlogs.tistory.com/27) 을 정리한 내용 입니다. 

---

 

0. 알고리즘: 컴퓨터 과학에서, 어떠한 문제를 해결하기 위한 방법

1. Big-O(이하 빅오): 알고리즘 간 효율성을 비교하기 위한 표기법

- 쉽게 설명하면 알고리즘의 효율성에 대한 표기

- 알고리즘의 효율성은 데이터 개수(n)가 수학 연산의 횟수

- 시간 복잡도(시간 효율성), 공간 복잡도(알고리즘의 공간 ~ 메모리)를 주로 표현함

 

1-1. 빅오 표기법 예제

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(): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
6. O() : 피보나치 수열

 

---

데이터 안에 for 문을 돌리면 2x 가 아니고 x² 이 된다.

삼중 for 문이면 x³ 이니까. 효율적인 알고리즘을 짜기 위해 고민하기.