근적인 방법을 사용하는 이유는, 같은 알고리즘이라도 입력 자료의 크기에 따라 수행 시간에 차이가 나는 것을 보완하기 위해서이다. 이런 수행 시간의 차이는 상수 배로 나타나는데, 이때의 상수를 숨은 상수 ( hidden constant ) 라고 한다. 시간 효율성의 추산은 수행 단계로서 정의하는 것에 의존한다. 의미있는 분석을 하려면, 각 단계에서 걸리는 수행 시간에 상한이 있어야 한다. 예를 들어, 두 수의 덧셈을 하나의 단계라 할 때, 각 수가 지극히 크면, 덧셈이 일정한 시간 내에 완료된다고 할 수 없기 때문이다. ( 2자리수의 덧셈을 하는 경우와 1000자리수의 덧셈을 하는 경우를 비교하여 생각해보라. ) 목차 1 비용 모델 2 실행 시간 분석 2. 1 실험적 측정법의 단점 2. 2 증가
알고리즘 분석 - 위키백과, 우리 모두의 백과사전 알고리즘 분석 위키백과, 우리 모두의 백과사전. ( 알고리즘 해석에서 넘어옴 ) 둘러보기로 가기 검색하러 가기 알고리즘 분석 ( 영어 : analysis of algorithms ) 은 컴퓨터 과학에서 알고리즘을 실행하는데 필요한 ( 시간과 기억 용량과 같은 ) 자원의 수를 결정하는 일을 가리킨다. 대부분의 알고리즘은 임의의 길이의 입력과 함께 동작하도록 구성된다. 일반적으로 알고리즘의 효율성과 실행 시간은 단계의 수 ( 시간 복잡도 ) 와 기억 위치 ( 공간 복잡도 ) 에 대한 입력 길이와 관련한 함수로 나타낼 수 있다. 알고리즘 분석이 더 광범위한 계산 복잡도 이론의 중요한 부분인데, 주어진 계산 문제를 해결하는 알고리즘에 필요한 자원에 대한 이론적 견적을 제공한다. 이러한 견적들은 효율적인 알고리즘을 검색하는데 도움을 준다. 알고리즘 분석에서
복잡도 이론의 중요한 부분인데, 주어진 계산 문제를 해결하는 알고리즘에 필요한 자원에 대한 이론적 견적을 제공한다. 이러한 견적들은 효율적인 알고리즘을 검색하는데 도움을 준다. 알고리즘 분석에서는 보통 점근적 ( asymptotic ) 의미로 복잡도를 계산한다. 즉, O표기법, [UNK], [UNK] 같은 방법으로 일정 크기의 입력 자료에 대한 복잡도 함수를 구한다. 예를 들어, 이진 탐색의 단계 수는 입력 자료의 크기에 대수적으로 비례하는데, 이것을 O ( log n ) { [UNK] displaystyle O ( [UNK] log n ) } 또는 대수 시간이라 한다. 점근적인 방법을 사용하는 이유는, 같은 알고리즘이라도 입력 자료의 크기에 따라 수행 시간에 차이가 나는 것을 보완하기 위해서이다. 이런 수행 시간의 차이는 상수 배로 나타나는데, 이때의 상수
는 O ( 2n ) 차수 이다. 이는 매우 빠르고 관리 불가능한 메모리 자원 소모 증가 비율이다. 중요성 [ 편집 ] 알고리즘 분석은 실제로 중요하다. 비효율적인 알고리즘의 우발적이거나 또는 고의가 아니 사용은 시스템 성능에 중요한 영향을 끼칠 것이다. 시간에 민감한 응용에서, 너무 오래 동작하는 알고리즘은 기한이 지나거나 쓸모없는 결과를 만들 수 있다. 비효율적인 알고리즘 역시 적인 계산 파워나 저장 공간을 요구하게 될 것이며 이 역시 실질적으로 쓸모없게 되버린다. 상수 인자 [ 편집 ] 특히 초급 단계에서 알고리즘 분석은 일반적으로 점근적 ( asymptotic ) 성능에 초점을 맞춘다, 그러나 실제 응용에서 상수 요소들은 중요하며 실제 데이터들은 항상 크기가 제한되 있다. 다룰수 있는 메모리의 크기가 다음과 같이 제한되어 있다 ; 32 - bit 장치
milliseconds 선형 검색 프로그램이 작동하는 컴퓨터 A는 선형 증가 비율을 보이고 있다. 그 프로그램의 실행 시간은 직접적으로 입력 크기에 비례한다. 입력 크기를 두 배로 하면 실행 시간도 두 배가 되고, 네 배로 증가하여도 마찬가지 이다. 반면에 이진 검색 프로그램이 작동하는 컴퓨터 B는 로그 ( logarithmic ) 증가 비율을 보인다. 네 배 증가된 입력은 실행 시간을 단지 상수만큼 ( 이 예제에서는 50, 000ns ) 증가 시킨다. 심지어 컴퓨터 A는 표면상으로 빠르지만, 실행시간 성능 측면에서 컴퓨터 B는 컴퓨터 A를 추월한다. 이는 컴퓨터 B에서 매우 낮은 증가 비율로 알고리즘이 작동하기 때문이다. 증가 차수 [ 편집 ] 만약 입력 크기가 n이고 함수 f ( n ) 와 양의 상수의 곱으로 알고리즘 실행 시간의 상한선 ( upper bound ) 을 제공한다
면, 위의 결론이 잘못됐다는 것이 입증 될 것이다 : n ( 리스트 크기 ) 컴퓨터 A 실행시간 ( ns ) 컴퓨터 B 실행시간 ( ns ) 16 8 100, 000 63 32 150, 000 250 125 200, 000 1, 000 500 250, 000......... 1, 000, 000 500, 000 500, 000 4, 000, 000 2, 000, 000 550, 000 16, 000, 000 8, 000, 000 600, 000......... 63, 072 x 1012 31, 536 x 1012 ns, or 1 year 1, 375, 000 ns, or 1. 375 milliseconds 선형 검색 프로그램이 작동하는 컴퓨터 A는 선형 증가 비율을 보이고 있다. 그 프로그램의 실행 시간은 직접적으로 입력 크기에 비례한다. 입력 크기를 두 배로 하면 실행 시간도
기계 작동에 할당한다. 대수 비용 모델 ( logarithmic cost model ) / 대수 비용 측정 ( logarithmic - cost measurement ) : 수반되는 비트의 수와 비례하여 비용을 모든 기계 작동에 할당한다. 대수 비용 모델은 사용하기 더 번거롭기 때문에 암호학 분야 등의 임의 밀도 연산 알고리즘 분석과 같이 필요할 때에만 이용한다. 실행 시간 분석 [ 편집 ] 실행 시간 분석은 입력 크기가 증가함에 따라 알고리즘의 실행 시간이 늘어나는 것을 측정하고 예측하는 이론적 분류이다. 실행 시간의 효율성은 컴퓨터 과학의 주된 관심사이다. 프로그램 하나는 실행을 마치는데 수 초, 수 시간, 수 년이 걸릴 수 있으며 이는 알고리즘의 수행 방식에 따라 결정된다. ( 성능 분석도 참고 ) 실험적 측정법의 단점 [ 편집 ] 알고리즘들은 플랫폼 - 독립적 ( platform -
croft ; Jeffrey D. Ullman ( 1974 ). 《 The design and analysis of computer algorithms 》. Addison - Wesley Pub. Co., section 1. 3 ↑ Juraj [UNK] ( 2004 ). 《 Theoretical computer science : introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography 》. Springer. 177 - 178쪽. ISBN 978 - 3 - 540 - 14015 - 3. ↑ Giorgio Ausiello ( 1999 ). 《 Complexity and approximation : combinatorial optimization problems and their approximability properties 》. Springer. 3 - 8쪽
, 수 시간, 수 년이 걸릴 수 있으며 이는 알고리즘의 수행 방식에 따라 결정된다. ( 성능 분석도 참고 ) 실험적 측정법의 단점 [ 편집 ] 알고리즘들은 플랫폼 - 독립적 ( platform - independent ) 이기 때문에 ( 예, 특정 알고리즘은 임의의 컴퓨터 및 운영체제에서 임의의 프로그램 언어로 구현될 수 있다 ), 여러 알고리즘들의 성능을 비교하기 위하여 실험적 접근법을 사용하는 것은 심각한 문제점을 가지고 있다. 크기가 n인 정렬된 리스트에서 특정 엔트리 ( entry ) 를 검색하는 프로그램을 예로 들어보자. 이 프로그램이 선형 검색 알고리즘으로 최신 컴퓨터 A에 구현되었고, 이진 검색 알고리즘으로 훨씬 느린 컴퓨터 B에 구현되어있다고 가정해보자. 두 컴퓨터에서 각자의 프로그램으로 벤치마크 ( Benchmark ) 테스트를 수행하고 다음과 같
은 증가 비율로 알고리즘이 작동하기 때문이다. 증가 차수 [ 편집 ] 만약 입력 크기가 n이고 함수 f ( n ) 와 양의 상수의 곱으로 알고리즘 실행 시간의 상한선 ( upper bound ) 을 제공한다면, 수학 함수의 차수로 알고리즘의 성장 비율을 보일 수 있다. 다시 말해서, 주어진 입력 크기 n이 0와 상수 c보다 클 경우, 알고리즘의 실행시간은 틀 : Tmath보다 결코 크지 않다. 이 개념은 Big O 표기법으로 주로 표현된다. 예를 들어 삽입 정렬의 실행 시간이 입력 크기에 따라 이차식으로 증가하기 때문에, 삽입 정렬은 O ( n2 ) 라 할 수 있다. Big O 표기법은 알고리즘의 최악의 경우 시나리오를 표현하는데 편리한 방법이며, 평균 경우를 표현 할 때도 활용 될 수 있다. 예를 들어 [UNK] 정렬의 최악의 경우 시나리오
알고리즘 분석(영어: analysis of algorithms)은 컴퓨터 과학에서 알고리즘을 실행하는데 필요한 (시간과 기억 용량과 같은) 자원의 수를 결정하는 일을 가리킨다. 대부분의 알고리즘은 임의의 길이의 입력과 함께 동작하도록 구성된다. 일반적으로 알고리즘의 효율성과 실행 시간은 단계의 수 (시간 복잡도)와 기억 위치 (공간 복잡도)에 대한 입력 길이와 관련한 함수로 나타낼 수 있다. 알고리즘 분석이 더 광범위한 계산 복잡도 이론의 중요한 부분인데, 주어진 계산 문제를 해결하는 알고리즘에 필요한 자원에 대한 이론적 견적을 제공한다. 이러한 견적들은 효율적인 알고리즘을 검색하는데 도움을 준다. 알고리즘 분석에서는 보통 점근적(asymptotic) 의미로 복잡도를 계산한다. 즉, O표기법, Ω표기법, Θ표기법과 같은 방법으로 일정 크기의 입력 자료에 대한 복잡도 함수를 구한다. 예를 들어, 이진 탐색의 단계 수는 입력 자료의 크기에 대수적으로 비례하는데, 이것을 O (log ⁡ n) {\displaystyle O(\log n)} 또는 대수 시간이라 한다. 점근적인 방법을 사용하는 이유는, 같은 알고리즘이라도 입력 자료의 크기에 따라 수행 시간에 차이가 나는 것을 보완하기 위해서이다. 이런 수행 시간의 차이는 상수 배로 나타나는데, 이때의 상수를 숨은 상수(hidden constant)라고 한다. 시간 효율성의 추산은 수행 단계로서 정의하는 것에 의존한다. 의미있는 분석을 하려면, 각 단계에서 걸리는 수행 시간에 상한이 있어야 한다. 예를 들어, 두 수의 덧셈을 하나의 단계라 할 때, 각 수가 지극히 크면, 덧셈이 일정한 시간 내에 완료된다고 할 수 없기 때문이다. (2자리수의 덧셈을 하는 경우와 1000자리수의 덧셈을 하는 경우를 비교하여 생각해보라.)