[Algorithm] 알고리즘 분석
🪐 정확성 분석
수학적 기법을 사용해 유효한 입력이 주어졌을 때 유한 시간 내에 예상한 대로 수행되어 정확한 결과를 생성하는지 증명
🪐 효율성 분석
-
알고리즘을 수행하는 데 얼마나 많은 컴퓨터 자원(메모리의 양, 수행시간)이 필요한가를 평가
-
알고리즘을 수행하는 데 얼마의 시간이 걸리는지, 얼마만큼의 메모리가 사용되는지 분석 → 이를 각각 시간 복잡도(time complexity), 공간 복잡도(space complexity)라고 함
-
효율적인 알고리즘 = 가능한 적은 메모리를 사용하고, 가능한 빠르게 수행되는 알고리즘
-
공간 복잡도
-
알고리즘 수행에 필요한 총 메모리의 양
-
정적 공간(컴파일 과정에서 고정적으로 결정) + 동적 공간(실행 과정에서 동적 할당이나 함수 호출 등을 통해 동적으로 결정)
-
-
시간 복잡도
-
알고리즘의 수행시간
-
컴퓨터의 속도, 프로그래밍 언어의 종류, 프로그램 작성 방법, 컴파일러 등 여러 실행 환경에 따라 달라질 수 있음
-
알고리즘 고유의 특성을 고려한 객관적인 측정 방법이 필요 → 기본 연산의 수행 횟수를 세는 방법을 사용해 계산
-
시간 복잡도 = 알고리즘에서 각각의 단위 연산들이 수행되는 횟수를 계산, 이를 모두 더한 값
-
입력 크기와 입력 데이터의 상태에 따라 결과가 달라질 수 있음
-
입력 크기(=입력 데이터의 개수)에 따라 수행시간이 달라지기 때문에 특정 입력 크기에 대한 단위 연산의 수행 횟수의 합으로 수행시간을 표현하기 보다는 입력 크기 n의 함수로 표현하는 것이 바람직
-
최선의 경우 : 가능한 모든 입력 상태의 수행시간 중 가장 빠른 시간, 알고리즘에 가장 적절하고 효과적인 형태로 데이터가 주어진 경우
-
최악의 경우 : 가능한 모든 입력 상태의 수행시간 중 가장 느린 시간, 어떠한 상태의 입력이 주어지더라도 이를 초과하는 수행시간은 걸리지 않는다는 것을 보장, 알고리즘 간의 성능을 비교할 때 유용 → 일반적으로 최악의 수행시간을 알고리즘의 시간 복잡도의 척도로 사용
-
🪐 점근성능(asymptotic performance)
-
입력 크기 n이 무한히 커짐에 따라 결정되는 성능
-
입력 크기 n에 대한 함수로 표현되는 시간 복잡도는 일반적으로 n에 대한 다항식으로 표현. 이때 상수는 연산의 종류와 컴퓨터 속도에 의해 좌우되는 값으로, 알고리즘의 우열을 평가할 때는 상수를 무시하고 입력 크기 n에 대한 차수만을 고려하는 것이 일반적
-
입력 크기가 무한대로 커질수록 수행시간은 최고 차수를 가진 항에 의해서 가장 큰 영향을 받아 결정됨 → 다항식 함수에서 최고차항만을 계수 없이 취해서 단순화시킨 형태로 성능을 표현
-
점근성능 사용 시 알고리즘의 정확한 수행시간은 알 수 없지만, 입력 크기가 증가함에 다라 수행시간이 어떤 식으로 증가하는지 식의 증가 추세를 쉽게 파악할 수 있어 알고리즘 간의 우열을 따질 때 유용
-
점근성능 표기 방법
-
Big-O(빅 오)
-
O(g(n)) 는 g(n)이라는 함수보다 증가율이 같거나 더 느린 함수들의 집합
-
최대 얼마나 걸리는지 = 최악의 경우
-
해당 알고리즘은 big-O 보다 더 오래 걸릴 수 없다
-
-
Big-Ω(빅 오메가)
-
Ω(g(n)) 는 g(n)이라는 함수보다 증가율이 같거나 더 빠른 함수들의 집합
-
최소 얼마만큼 걸렸는지 = 최선의 경우
-
해당 알고리즘은 big-Omega 보다 더 빠를 수 없다
-
-
Big-θ(빅 세타)
-
θ(g(n)) 는 g(n)이라는 함수와 증가율이 같은 함수들의 집합
-
평균적인 경우
-
big-O 와 big-Omega 를 하나로 합쳐 표현한 것과 같다
-
-
-
-
증가율이 더 빠르다 = 알고리즘이 더 느리게 수행됨
-
증가율이 더 느리다 = 알고리즘이 더 빠르게 수행됨
-