알고리즘이란?
어떤 문제나 목적을 달성하기 위해 거쳐야 하는 여러 과정들을 의미한다.
이 과정들은 다양하고, 상황에 따라 알고리즘은 모두 다르다.
따라서 상황에 맞게 시간 복잡도가 가장 낮은 알고리즘을 선택하여 사용한다.
(효율적이고 사용 환경에 최적인 알고리즘을 선택하여 사용한다.)
일반적으로 알고리즘의 성능 분석은 실행에 필요한 공간 측면에서 분석하는 공간 복잡도,
실행 소요시간 측면에서 분석하는 시간 복잡도를 추정하여 평가를 한다.
알고리즘의 실행 시간이란?
알고리즘의 실행 시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존한다.
이 속도는 컴퓨터의 처리속도, 사용된 언어 종류, 컴파일러 속도에 달려있다.
알고리즘의 실행 시간을 두 부분으로 나누면 다음과 같다.
- 입력값의 크기에 따른 알고리즘의 실행시간
- 입력값의 크기에 따른 함수의 증가량,즉 성장률(rate of growth)을 의미한다. 이 때 중요하지 않은 부분을 제거하면 알고리즘의 실행 시간에서 중요한 부분인 성장률에 집중할 수 있다. 이렇게 제거한 것을 점근적 표기법(asymptotic notation)이라 한다.
점근적 표기법은 다음 3가지 형태가 있다.
- 최상의 경우 : 오메가 표기법(Big-Ω)
- 평균의 경우 : 세타 표기법(Big-θ)
- 최악의 경우 : 빅오 표기법(Big-O)
평균인 세타를 쓰면 좋겠지만 매우 까다롭기 때문에 최악인 상황을 사용하게 된다.
최악일 경우를 판단하면 평균과 가까운 성능으로 예측하기 쉽기 때문이다.
빅오 표기법(Big-O)란?
알고리즘 성능을 수학적으로 표기해주는 표기법이다.
알고리즘의 실행시간보다는 데이터나 사용자 증가률에 따른 알고리즘 성능을 예측하는게 목표이므로 중요하지 않은 부분인 상수와 같은 숫자는 모두 제거한다.
즉, 빅오 표기법은 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용된다.
여기서 측정되는 복잡성에는 시간 복잡도와 공간 복잡도가 있다.
- 시간 복잡도 : 입력되는 n의 크기에 따라 실행되는 조작의 수
- 공간 복잡도 : 알고리즘이 실행될 때 사용하는 메모리 양 (메모리 발전으로 중요도 낮아지는 중)
아래 사진은 대표적인 Big-O의 복잡도를 나타내는 차트이다.
시간 복잡도
시간 복잡도의 가장 간단한 정의는 알고리즘의 성능을 설명하는 것이다.
따라서 시간 복잡도는 프로세스가 수행해야하는 연산을 수치화한 것이라고 볼 수 있다.
컴퓨터 성능에 따라 실행시간은 달라질 수 있으므로 실제 실행 시간보다는 명령문의 실행 빈도수를 계산하여 실행 시간을 구하게 된다.
그렇다면 이제 빅오 표기법의 예를 살펴보자.
O(1)
Constant Time (상수)
입력 데이터 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘이다.
n[0]이 0이면 true, 0이 아니면 false를 반환한다.
데이터가 증가함에도 성능에는 변함없이 일정함을 나타내고 있다.
O(n)
Linear Time (선형)
입력 데이터의 크기에 비례해서 처리 시간이 걸리는 알고리즘이다.
n이 1번 늘어날 때마다 처리시간이 1 증가하여 선형적으로 증가한다.
(n 크기만큼 처리시간이 증가)
데이터와 시간이 같은 비율로 증가함을 볼 수 있다.
O(n^2)
Quadratic Time
입력 데이터 n만큼 반복하는데, 그 안에서 n만큼 또 반복할 때의 표기 방법이다.
데이터가 적을 때는 문제 없지만 많아질수록 수직상승한다.
n만큼 반복하면서 그 안에서도 n만큼 반복하니까, 처리횟수가 n을 가로와 세로 길이로 가지는 면적만큼 늘어나게 된다.
n이 증가할 때마다 가로와 세로 한 줄이 증가하므로 데이터가 커질수록 처리시간이 부담된다.
처음은 미미하지만 어느 순간부터 수직상승을 하는 것을 볼 수 있다.
O(nm)
Quadratic Time
바로 위 O(n^2)와 비슷하지만 다르다. n만큼 2번 반복하는 것이 아니라 n을 m만큼 반복한다.
n> m 또는 n < m 이런 상황이 발생할 수 있다.
O(n^2)랑 비슷하지만 n이 엄청 클수도 있고, m이 엄청 작을 수도 있다.
따라서 그래프도 O(n^2)랑 비슷하지만 상황에 따라 다르게 그려줘야한다.
O(n^3)
Polynomial / Cubic Time
n을 3중으로 반복한다. 따라서 큐빅과 같은 구조를 뛴다.
O(n)일 때는 직선 (1차원)
O(n^2)일 때는 면적 (2차원)
O(n^3)일 때는 큐빅 (3차원)
O(n^2)랑 비슷한 형태이지만 데이터가 증가할 때마다 더 급격하게 처리시간이 늘어난다.
O(2^n)
Exponential Time
피보나치(Fibonacci) 수열로 비유할 수 있다.
피보나치 수열은 1에서 시작하여 한 면을 기준으로 정사각형을 만드는 것이다.
위 그림에서 1 -> 1 -> 2 -> 3 -> 5 -> 8 -> ....
이런식으로 그리다보면 황금 비율인 피보나치 나선형이 그려진다.
수학적으로 접근하면 다음과 같다.
- 0 + 1 = 1
- 1 + 1 = 2
- 1 + 2 = 3
- 2 + 3 = 5
- 3 + 5 = 8
- ....
이걸 Java(자바)로 표현하면 다음과 같은 재귀 함수가 만들어진다.
위 함수를 예시로 fibonacci(5, r) 을 넣었다고 생각하면 다음과 같이 결과가 나온다.
매번 함수가 호출될 때마다 2번씩 호출하게 된다.
이 호출하는 횟수는 트리의 높이만큼 반복된다. 따라서 O(2^n)의 시간 복잡도를 가지게 된다.
즉, 모든 함수의 호출을 일일이 계산해야 한다.
이 설명은 피보나치 수열을 자바 함수로 만든 2번째 버전과 동일하다.
만약 1번째 버전처럼 배열을 만들어서 값을 넣어놓는다면 (함수의 값을 저장한다면) 똑같은 함수를 계속 호출하여 계산할 필요가 없다.
따라서 순환 호출이 일어나서 트리의 높이(k)만큼 반복될 때 함수의 중복 호출을 모두 없애버리기에 O(n)이 된다.
O(m^n)
Exponential Time
m개씩 n번 늘어나는 알고리즘이다. 이것은 바로 위 O(2^n)에서 2대신에 m을 넣어서 표현하면 된다.
Math.pow(밑, 지수) 인 제곱함수이다. 예를 들면 m = 2 , n = 4 를 넣으면 16이 나온다.
O(log n)
O(log n)의 대표적인 알고리즘은 이진 검색(binary search)이다.
위 사진에서 정렬된 숫자 1~9에서 key값이 6인 숫자를 검색하는 것을 보여주고 있다.
처음 중간인 5부터 확인하여 비교한다. key값이 더 크므로 왼쪽은 비교할 필요가 없고, 오른쪽만 비교한다.
오른쪽에서 중간인 7을 비교한다. key값이 더 작으므로 오른쪽은 비교할 필요가 없고, 왼쪽만 비교한다.
남은 공간에서 중간인 6을 비교한다. key값과 동일하므로 종료한다.
이런 식으로 데이터를 한 번 찾을 때마다 반틈씩 없어지는 알고리즘을 O(log n) 이라고 한다.
이런 방식은 순차 검색 O(n)보다도 훨씬 빠르다.
데이터가 증가해도 크게 성능이 차이나지 않는다.
O(sqrt(n))
Square Root (제곱근)
- 100의 제곱근은 10
- 9의 제곱근은 3
그림으로 그려보면 위 사진과 같다.
- n = 9일 때, sqrt(n)은 사각형의 첫번째 줄의 개수 3이 제곱근이다.
- n = 16일 때, sqrt(n)은 사각형의 첫번째 줄의 개수 4가 제곱근이다.
- n = 25 일 때, sqrt(n)은 당연히 규칙적으로 5가 제곱근이다.
📝
빅오 표기법 (Big O notation)에서는 상수는 표현하지 않는다.
제일 처음에도 말했듯이 알고리즘의 실행시간보다는 데이터 증가률에 따른 알고리즘 성능을 예측하는게 목표이다.
따라서 중요하지 않은 부분인 상수와 같은 숫자는 모두 제거하여 표현한다.
상수는 고정된 숫자이기에 언제나 고정된만큼만 증가하므로 신경쓰지 않는다.
https://blog.chulgil.me/algorithm/
https://www.youtube.com/watch?v=6Iq5iMCVsXA
'코딩테스트 > 알고리즘' 카테고리의 다른 글
| 그리디 알고리즘(Greedy Algorithm)이란? (0) | 2022.07.15 |
|---|---|
| 삽입 정렬(Insertion Sort)이란? (0) | 2022.07.11 |
| 버블정렬(Bubble Sort)이란? (0) | 2022.07.10 |
| 선택정렬(Selection Sort)이란? (0) | 2022.07.10 |