알고리즘에 대해 정리하기에 앞서 Big-O 표기법에 대해 먼저 정리해보고자 한다.
Big-O 표기법이란?
알고리즘에서 사용되는 Big-O 표기법은 알고리즘의 성능을 분석하고 비교하기 위해 사용되는 표기법으로 알고리즘의 시간 복잡도(실행 시간) 또는 공간 복잡도를 나타내는데 사용된다.
Big-O 표기법은 주어진 입력 크기에 대한 알고리즘의 실행 시간 또는 공간 요구 사항을 표현한다.
Big-O는 "O"라는 기호와 함께 표기되며, O 다음에는 함수가 나온다. 이 함수는 주어진 입력 크기에 대한 알고리즘의 실행 시간 또는 공간 복잡도를 나타낸다.
Big-O 표기법에서는 주로 최악의 경우 시간 복잡도를 나타낸다.
즉, 입력 크기에 따라 알고리즘의 실행 시간이 어떻게 증가하는지, 그 중 '아무리 많이 걸려도 최대 이 시간 안에는 끝난다는 것’을 나타낸다.
다른 표기법으로는 최선의 경우 시간 복잡도나 평균 시간 복잡도도 있을 수 있다.
시간 복잡도 / 공간 복잡도
우선 계속해서 언급된 시간 복잡도와 공간 복잡도에 대해 먼저 정리해보자.
시간 복잡도와 공간 복잡도는 알고리즘의 성능을 분석하기 위해 사용되는 두 가지 주요 개념이다.
시간 복잡도(Time Complexity)
시간 복잡도는 알고리즘이 주어진 입력 크기에 대해 얼마나 많은 시간을 소요하는지를 나타내는 것이다.
일반적으로 Big-O 표기법을 사용해 나타내며, 입력 크기에 따라 실행 시간이 어떻게 증가하는지를 나타낸다.
시간 복잡도는 알고리즘의 효율성을 평가하고 알고리즘 간의 상대적인 성능을 비교하는 데 사용된다.
공간 복잡도(Space Complexity)
공간 복잡도는 알고리즘이 실행되는 동안 얼마나 많은 메모리 공간을 사용하는지를 나타낸다.
마찬가지로 Big-O 표기법을 사용하여 나타내며, 입력 크기에 따라 필요한 공간의 양이 어떻게 증가하는지를 나타낸다.
공간 복잡도는 알고리즘이 메모리를 얼마나 효율적으로 사용하는지를 평가하는 데 사용된다.
시간 복잡도와 공간 복잡도는 알고리즘의 성능 측면에서 서로 다른 관점을 제공한다.
알고리즘을 설계할 때에는 시간 복잡도(실행 시간)와 메모리 사용량 간의 균형을 고려해야 한다.
일부 알고리즘은 빠른 실행 시간을 제공하면서도 많은 메모리를 사용하고, 다른 알고리즘은 적은 메모리를 사용하면서도 실행 시간이 길어질 수 있다.
따라서 시간 복잡도와 공간 복잡도를 모두 고려해 알고리즘을 선택하고 최적화하는 것이 중요하다.
Big-O 표기법의 일반적인 표기법
Big-O 표기법에서 가장 일반적인 표기법은 다음과 같다.
아래에서 사용되는 n은 입력되는 데이터를 의미한다.
또한, Big-O 표기법 순서는 시간 복잡도가 좋은 순서대로 나열했다.
- O(1) : 상수 시간 복잡도를 의미한다. 입력 크기와 관계없이 실행 시간이 일정하다. 예를 들어, 배열에서 특정 인덱스의 요소를 찾는 것은 상수 시간이 소요된다.
- O(log₂ n) : 로그 시간 복잡도를 의미한다. 실행 시간이 입력 크기의 로그에 비례한다. 이는 주로 이진 검색과 같이 입력을 반씩 나누는 알고리즘에서 나타난다.
- O(n) : 선형 시간 복잡도를 의미한다. 입력 크기에 비례해 선형적으로 증가한다. 예를 들어, 배열의 모든 요소를 한 번씩 방문하는 것은 선형 시간이 소요된다.
- O(n log₂ n) : 선형 로그 시간 복잡도를 의미한다. 입력 크기에 비례해 실행 시간이 증가하지만, 로그 요소도 추가된다. 이것은 입력 크기에 따라 연산의 횟수가 증가하지만, 이 증가는 로그 함수의 성질에 따라 상대적으로 느리게 증가함을 말한다. 주로 효율적인 정렬 알고리즘인 병합 정렬과 퀵 정렬에서 나타난다.
- O(n²) : 이차 시간 복잡도를 의미한다. 입력 크기의 제곱에 비례해 증가한다. 이는 주로 이중 반복문이 있는 알고리즘에서 나타난다.
- O(2ⁿ) : 지수 시간 복잡도를 의미한다. 입력 크기에 대해 2의 거듭제곱에 비례해 증가한다. 이는 주로 완전 탐색과 같이 가능한 모든 경우의 수를 확인해야 하는 알고리즘에서 나타난다.
이외에도 더 많은 Big-O 표기법이 있으며, 알고리즘의 성능 분석을 위해 사용된다.
Big-O 표기법은 알고리즘 간의 상대적인 성능을 비교하거나 알고리즘의 효율성을 평가하는 데 도움되며 많이 사용된다.
시간 복잡도 줄이는 방법
적절한 자료구조 사용
시간 복잡도를 줄이기 위해서는 적절한 자료구조를 사용하는 것이 좋다.
아래의 표는 자료구조에 대한 시간 복잡도다.
이를 참고해 가장 효율적인 자료구조를 적절히 사용한다면 시간 복잡도를 줄일 수 있을 것이다.
적절한 알고리즘 사용
시간 복잡도를 줄이기 위한 방법에는 적절한 알고리즘을 사용하는 방법도 있다.
알고리즘에는 그리디 알고리즘, 정렬 알고리즘 등이 있다.
자료구조와 마찬가지로 알고리즘도 잘 익힌 뒤 적절할 때 사용하면 시간 복잡도를 줄일 수 있을 것이다.
아래는 배열의 정렬 알고리즘 시간 복잡도를 나타낸다.
'자료구조 & 알고리즘' 카테고리의 다른 글
| [자료구조] Tree 순회 방법 - 전위/중위/후위 순회 & Java 예시 코드 (0) | 2023.08.06 |
|---|---|
| [백준] 11729 하노이 탑 이동순서 풀이 (0) | 2023.08.06 |
| [자료구조] 해시 테이블(Hash Table) 자료구조 알아보기 & Java 예제 코드 (0) | 2023.06.11 |
| [자료구조] 트리(Tree) 자료구조 알아보기 & Java 예제 코드 (0) | 2023.06.10 |
| [자료구조] 그래프(Graph) 자료구조 알아보기 & Java 예제 코드 (0) | 2023.06.10 |
