1. 시간복잡도
- 알고리즘이 문제를 해결하기 위한 수행시간의 분석 결과인
시간,연산의 횟수(스탭수) - 주로 최악의 경우(worst case)를 따져 Big O 표기법을 이용해 분석
2. 공간복잡도
- 알고리즘의 메모리 사용량에 대한 분석 결과
주로 최악의 경우(worst case)를 따져 Big O 표기법을 이용해 분석
- 공간복잡도가 커졌을 경우?
- 공간 복잡도는 보통 시간 복잡도보다 중요하게 생각되지 않는 경우가 많다.
그러나 빅데이터 처리를 하는 경우, 공간 복잡도가 위와 같이 커지게 된다면,
메모리에 한 번에 올라가지 않아 프로그램을 실행할 수 없는 문제가 발생할 수 있다.
이 경우, 데이터를 나눠서 처리하고 다시 합치는 방법을 사용하게 된다.
3. Big O 표기법
Big-Oh Notation
예를 들어, 동전을 튕겨 뒷면이 나올 확률을 이야기 할 때
운이 좋으면 1번에 뒷면이 나오지만
운이 안 좋다면 n번 만큼 동전을 튕겨야 하는 경우가 발생한다.
이 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라 부른다.
- 알고리즘의 효율성을 상한선 기준으로 표기해주는 표기법
- 값이 클수록, 그래프가 위로 향할수록 비효율적임을 의미
빅오(Big-O), 빅오메가(big-Ω),빅세타(big-Θ) 표기법
- 빅오: 상한선 기준
- 빅오메가: 하한선을 기준
- 빅세타: 상한선과 하한선의 사이를 기준
3-1. Big-O 표기법의 종류
3-1-1. O(1)
constant complexity
- 입력값이 증가하더라도 시간이 늘어나지 않는다.
- 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다.
3-1-2. O(n)
linear complexity
- 입력값이 증가함에 따라 시간 또한 같은 비율로 증가
예) 1중 for문
3-1-3. O(log n)
logarithmic complexity
- O(1) 다음으로 빠른 시간 복잡도를 가짐
- 예) 자료구조에서 Binary Search Tree
ㄴ 2진 탐색트리는 노드를 이동할때마다 경우의 수가 절반으로 줄어든다.
3-1-4. O(n^2)
quadratic complexity
- 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가
예) 2중 for문
3-1-5. O(2^n)
exponential complexity
- Big-O 표기법 중 가장 느린 시간 복잡도를 갖음
- O(log n)복잡도 같은 경우는 선택할때마다 경우의 수가 절반으로 줄어들었지만,
O (2^n)복잡도는 그 반대로 경우의 수가 2배씩 들어난다.
3-2 시간복잡도를 구하는 요령
- 하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)
- 컬렉션의 절반 이상 을 반복 하는 경우 : O (n / 2) -> O (n)
- 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 : O (n + m) -> O (n)
- 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)
- 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O (n * m) -> O (n²)
- 컬렉션 정렬을 사용하는 경우 : O(n*log(n))
—
*빅-오 표기법 (Big-Oh Notation) O(n) 시간복잡도 함수 T(n)T(n)에서 가장 영향력이 큰 부분만을 따지는 표기법
*https://lgphone.tistory.com/46
(참고)
공부한 내용을 여러글과 책 읽은 내용을 바탕으로 정리하고 있습니다.
좋은 글로 저의 공부에 도움을 주시는 분들께 감사드립니다.