빅오 표기법 (big O notation)
요즘 알고리즘 스터디도 하고 프로그래머스 코딩테스트를 풀고있다.
문제를 마주쳤을 때 문제에 대해 이해도 못했을 뿐만 아니라 그 문제를 어떻게 풀어야되지 라는 막막함도 있었다.
그리고 문제가 해결했을 때 모든 코드의 분석과 해답은 프로그래머스에서 정답이냐 탈락이냐 거기에만 맡겼다.
하지만 내 넘겨 받는 데이터의 갯수가 예시에서는 5개지만 최대 100,000개 까지 넘어온다고 했을 때
나의 코드는 100,000번 연산을 해서 값을 리턴하게 된다.
이러한 점에서 Big O 표기법을 지키며 코드를 작성해야겠다 라고 마음 먹었다.
| 빅오 표기법 이란?
알골리즘의 효율성을 의미한다.
효율성은 데이터의 갯수에 따라 기본 연산의 횟수를 의미한다.
예를 들어서 택배 트럭에 택배상자가 3개만 있고 트럭에는 총 500개 까지 들어갈 수 있다.
현재 택배에는 3개의 택배상자만 있으니 기사님이 택배를 내리는데 10초에서 20초 사이라고 가정해보자
예를 들어 "택배기사님이 택배를 하나 하나씩 내린다" 라는 정답이 나왔다고 한다면 정답이긴 하지만 좋은 정답은 아니다.
왜냐하면 트럭에 예를 들어서 500개의 택배가 전부 채워져있다면 기사님께서 하나하나 내렸을 때의 시간은 3개와 비교했을 때 엄청 오래 걸릴 것이고 기사님도 엄청난 에너지를 소비하게 된다.
빅 오 표기법은 시간 복잡도 / 공간 복잡도를 나타낸다.
시간 복잡도는 알고리즘의 시간 효율성이고 공간 복잡도는 메모리의 효율성이다.
즉 시간 복잡도는 택배를 내리는 시간이고 공간 복잡도는 기사님께서 얼마만큼의 에너지를 소비하는지를 나타낸다.
빅 오 표기법은 항상 최악의 시나리오(상한 값)을 다룬다.
| O(1)
입력값이 증가해도 실행시간은 동일한 알고리즘이다.
index로 접근하며 바로 처리할 수 있는 연산 과정의 시간 복잡도 -> 기본 연산 수 이다.
데이터가 1000개 라도 O(1)이 될 수 있고 1개라도 O(1) 이 될 수 있다.
- 스택에서의 push, pop
| O(log N)
데이터가 두 배로 증가 할 때마다 한 단계 씩 늘어나는 알고리즘이다.
즉 연산이 한 번 실행될 때 마다 테이터의 크기가 절반 씩 감소하는 알고리즘이다.
- 이진트리
| O(N)
100개에 원소가 있을 때 100개의 단계가 필요한 알고리즘이다.
for 문에서 두번째 인자에는 언제까지 실행 할 것인지를 명시해줘야 한다.
여기서 1000번 이라고 적으면 총 1000번을 순회하고 for 내부에 있는 연산을 1000번 진행한다.
- 반복문, 배열 검색
| O(N log N)
O(N) 과 O(log N) 알고리즘이 중첩 된 형태의 알고리즘이다.
효율적인 정렬 알고리즘의 시간 복잡도로 사용된다.
n의 제곱보다 빠르게 증가하는 함수이며 매우 큰 데이터 세트에서 계산의 효율성을 향상 하기 위해 사용 된다.
- 병합 정렬, 퀵 정렬
| O(N^2)
O(N log N) 과 같이 O(N) 과 O(log N) 알고리즘이 중첩 된 형태의 알고리즘이다.
입력 크기에 대한 함수로서 n의 제곱에 비례한다는 것을 나타낸다.
입력 크기에 대해 이차 시간 복잡도를 가지며 입력 크기가 증가함에 따라 계산 시간이 제곱으로 증가한다.
비효율적인 알고리즘이며 그 이유는 입력 크기가 큰 경우에는 계산시간이 급격하게 증가 할 수 있다.
작은 데이터 세트에서 사용하면 상대적으로는 빠를 수 있지만 대규모의 데이터에는 부적합 하다.
- 이중 for문, 선택 정렬, 버블 정렬
| O(2^N)
빅 오 표기법 중 가장 느린 시간 복잡도이다.
지수 시간 복잡도를 나타내는 표기법이며 2의 N승에 비례하는 계산 시간을 나타낸다.
입력 크기가 증가함에 따라서 계산 시간이 기하급수적으로 증가하는 경우에 사용된다.
- 부분 집합 생성, 완전 탐색
| 실행 속도
위의 그래프에서 보는 것 처럼
O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N)
이렇게 빠른 알고리즘부터 느린 알고리즘 까지 정리했다.
빅 오 표기법을 지키며 코드를 작성하는 습관을 들여야겠다.
항상 최악의 상황을 먼저 생각하며 문제에 접근하고 최적의 코드를 작성해야겠다고 느꼈다.