1. [ 빅오 표기법 ]
빅오 표기법은 알고리즘의 효율성을 표기해주는 표기법이다.
쉽게 생각하면 알고리즘 스카우터라 생각하면 된다 :)
알고리즘의 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈 같은 기본 연산의 횟수를 의미한다.
빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용 된다.
(시간 복잡도는 알고리즘의 시간 효율성을 의미하고, 공간 복잡도는 알고리즘의 공간(메모리) 효율성을 의미한다.)
그런데 시간과 공간 복잡도를 나타내는 방법으로는 점근 표기법이라고 해서
빅오(Big-O),빅세타(big-Θ), 빅오메가(big-Ω) 표기법이 있다.
•
빅오 : 최악의 경우
•
빅세타 : 최악의경우 와 최선의 경우가 같을 때 ( 최악의경우 == 최선의 경우 )
•
빅오메가 : 최선의 경우
최선의 경우인 빅오메가를 잘 사용하지 않고 최악의 경우인 빅오를 잘 사용한다
빅오 : O(n) 를 많이 사용함
[ 빅오 여러 예제 ]
빅오 표기법의 예제는 어떤 것들이 있는지 정도만 외워두고 알고리즘 공부를 해보면서 이해해 나가면 될 것 같다. 아래 순서대로 내려가면 내려갈수록 비효율적이라는 것을 기억하자
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^2): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
6. O(2^n) : 피보나치 수열
