알고리즘 분석 - 위키백과, 우리 모두의 백과사전 알고리즘 분석 위키백과, 우리 모두의 백과사전. ( 알고리즘 해석에서 넘어옴 ) 둘러보기로 가기 검색하러 가기 알고리즘 분석 ( 영어 : analysis of algorithms ) 은 컴퓨터 과학에서 알고리즘을 실행하는데 필요한 ( 시간과 기억 용량과 같은 ) 자원의 수를 결정하는 일을 가리킨다. 대부분의 알고리즘은 임의의 길이의 입력과 함께 동작하도록 구성된다. 일반적으로 알고리즘의 효율성과 실행 시간은 단계의 수 ( 시간 복잡도 ) 와 기억 위치 ( 공간 복잡도 ) 에 대한 입력 길이와 관련한 함수로 나타낼 수 있다. 알고리즘 분석이 더 광범위한 계산 복잡도 이론의 중요한 부분인데, 주어진 계산 문제를 해결하는 알고리즘에 필요한 자원에 대한 이론적 견적을 제공한다. 이러한 견적들은 효율적인 알고리즘을 검색하는데 도움을 준다. 알고리즘 분석에서는 보통 점근적 ( asymptotic ) 의미로 복잡도를 계산한다. 즉, O표기법,, 같은 방법으로 일정 크기의 입력 자료에 대한 복잡도 함수를 구한다. 예를 들어, 이진 탐색의 단계 수는 입력 자료의 크기에 대수적으로 비례하는데, 이것을 O ( log n ) { displaystyle O ( log n ) } 또는 대수 시간이라 한다. 점
##playstyle f ( n ) = T - { 1 } T - { 2 } T - { 3 } T - { 7 } ( n1 ) T - { 4 } left [ { frac { 1 } { 2 } } ( n ^ { 2 } n ) right ] T - { 6 } left [ { frac { 1 } { 2 } } ( n ^ { 2 } 3n ) right ] T - { 5 } } 이는 다음과 같이 축소 되며 f ( n ) = [ 1 2 ( n 2 n ) ] T 6 [ 1 2 ( n 2 3 n ) ] T 5 ( n 1 ) T 4 T 1 T 2 T 3 T 7 { displaystyle f ( n ) = left [ { frac { 1 } { 2 } } ( n ^ { 2 } n ) right ] T - { 6 } left [ { frac { 1 } { 2 } } ( n ^ { 2 } 3n ) right ] T - { 5 } ( n1 ) T - { 4 } T - { 1 } T - { 2 } T - { 3 } T - { 7 } } 주어진 함수에서 가장 높은 차수항이 증가률을 결정하기 때문에 이를 실행시간 차수로 정의한다. 이 예제에서 n2는 가장 높은 차
1 T 2 T 3 T 7 ( n 2 n ) T 6 ( n 2 3 n ) T 5 ( n 1 ) T 4 T 1 T 2 T 3 T 7 ( for n 0 ) { displaystyle { begin { aligned } & left [ { frac { 1 } { 2 } } ( n ^ { 2 } n ) right ] T - { 6 } left [ { frac { 1 } { 2 } } ( n ^ { 2 } 3n ) right ] T - { 5 } ( n1 ) T - { 4 } T - { 1 } T - { 2 } T - { 3 } T - { 7 } leq & ( n ^ { 2 } n ) T - { 6 } ( n ^ { 2 } 3n ) T - { 5 } ( n1 ) T - { 4 } T - { 1 } T - { 2 } T - { 3 } T - { 7 } ( { text { for } } n geq 0 ) end { aligned } } } k는 [ T1.. T7 ] 보다 크거나 같은 상수라 가정하면 T 6 ( n 2 n ) T 5 ( n 2 3 n ) ( n 1 ) T 4 T 1 T 2 T 3 T 7 k ( n 2 n
##을 O ( log n ) { displaystyle O ( log n ) } 또는 대수 시간이라 한다. 점근적인 방법을 사용하는 이유는, 같은 알고리즘이라도 입력 자료의 크기에 따라 수행 시간에 차이가 나는 것을 보완하기 위해서이다. 이런 수행 시간의 차이는 상수 배로 나타나는데, 이때의 상수를 숨은 상수 ( hidden constant ) 라고 한다. 시간 효율성의 추산은 수행 단계로서 정의하는 것에 의존한다. 의미있는 분석을 하려면, 각 단계에서 걸리는 수행 시간에 상한이 있어야 한다. 예를 들어, 두 수의 덧셈을 하나의 단계라 할 때, 각 수가 지극히 크면, 덧셈이 일정한 시간 내에 완료된다고 할 수 없기 때문이다. ( 2자리수의 덧셈을 하는 경우와 1000자리수의 덧셈을 하는 경우를 비교하여 생각해보라. ) 목차 1 비용 모델 2 실행 시간 분석 2. 1 실험적 측정법의 단점 2. 2 증가 차수 2. 3 실험적 증가 차수 2. 4 실행시간 복잡도 평가 2. 5 다른 자원들의 증가 비율 분석 3 중요성 4 상수 인자 5 같이 보기 6 참조 비용 모델 [ 편집 ] 시간 효율 추정은 한 단계를 무엇으로 정의 하는지에 달려 있다. 실제 실행 시간과 실질적으로 부합
} } 이기 때문에 계수 a는 a = log ( t 2 / t 1 ) / log ( n 2 / n 1 ) { displaystyle a = log ( t - { 2 } / t - { 1 } ) / log ( n - { 2 } / n - { 1 } ) } 과 같다. 다시 말해, 실행시간 - 문제크기의 로그 - 로그 그래프에서 실험적 라인의 경사도를 측정 할 수 있다. 만약 증가 차수가 실제로 다항식의 미적분을 따른다면, 그 실험적 a 값은 다른 범위에서 상수로 유지 될 것이고, 아니면 바뀔 것이다. 위의 표 내용을 적용하면 다음과 같다 : n ( 리스크 크기 ) 컴퓨터 A 실행시간 ( ns ) 증가 지역 차수 ( n ^ - ) 컴퓨터 B 실행시간 ( ns ) 증가 지역 차수 ( n ^ - ) 15 7 100, 000 65 32 1. 04 150, 000 0. 28 250 125 1. 01 200, 000 0. 21 1, 000 500 1. 00 250, 000 0. 16......... 1, 000, 000 500, 000 1. 00 500, 000 0. 10 4, 000, 000 2, 000, 000 1. 00 550, 000 0. 07 16, 000, 000 8, 000, 000 1. 00 600, 000 0. 06
iterated logarithm ) ( log * ) 는 모든 실제 데이터 ( 265536 bits ) 에서 5보다 작다 ; ( 이진 ) log - log ( log log n ) 은 거의 모든 실제 데이터 ( 264 bits ) 에서 6보다 작다 ; 그리고 이진 log ( log n ) 은 거의 모든 실제 데이터 ( 264 bits ) 에서 64보다 작다. 실제 데이터에서 상수가 아닌 복잡도를 가지는 알고리즘은 상수 복잡도를 가지는 알고리즘 보다 더 효율적이다. 같이 보기 [ 편집 ] 점근 표기법 마스터 정리 NP - 완전 다항 시간 참조 [ 편집 ] ↑ Alfred V. Aho ; John E. Hopcroft ; Jeffrey D. Ullman ( 1974 ). 《 The design and analysis of computer algorithms 》. Addison - Wesley Pub. Co., section 1. 3 ↑ Juraj ( 2004 ). 《 Theoretical computer science : introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography 》. Springer. 177 - 178쪽. ISBN 978 - 3 - 540 - 14015 - 3. ↑ Giorgio
대수 비용 모델은 사용하기 더 번거롭기 때문에 암호학 분야 등의 임의 밀도 연산 알고리즘 분석과 같이 필요할 때에만 이용한다. 실행 시간 분석 [ 편집 ] 실행 시간 분석은 입력 크기가 증가함에 따라 알고리즘의 실행 시간이 늘어나는 것을 측정하고 예측하는 이론적 분류이다. 실행 시간의 효율성은 컴퓨터 과학의 주된 관심사이다. 프로그램 하나는 실행을 마치는데 수 초, 수 시간, 수 년이 걸릴 수 있으며 이는 알고리즘의 수행 방식에 따라 결정된다. ( 성능 분석도 참고 ) 실험적 측정법의 단점 [ 편집 ] 알고리즘들은 플랫폼 - 독립적 ( platform - independent ) 이기 때문에 ( 예, 특정 알고리즘은 임의의 컴퓨터 및 운영체제에서 임의의 프로그램 언어로 구현될 수 있다 ), 여러 알고리즘들의 성능을 비교하기 위하여 실험적 접근법을 사용하는 것은 심각한 문제점을 가지고 있다. 크기가 n인 정렬된 리스트에서 특정 엔트리 ( entry ) 를 검색하는 프로그램을 예로 들어보자. 이 프로그램이 선형 검색 알고리즘으로 최신 컴퓨터 A에 구현되었고, 이진 검색 알고리즘으로 훨씬 느린 컴퓨터 B에 구현되어있다고 가정해보자. 두 컴퓨터에서 각자의 프로그램으로 벤치마크 ( Benchmark ) 테스트를 수행하고 다음과 같은 결과를 얻었다 : n (
메뉴 개인 도구 로그인하지 않음토론기여계정 만들기로그인 이름공간 문서토론 변수 보기 읽기편집역사 보기 더 보기 검색 둘러보기 대문사용자 모임요즘 화제최근 문서 보기임의 문서로도움말기부 도구 여기를 가리키는 문서가리키는 글의 최근 올리기특수 문서 목록고유 링크문서 정보위키데이터 항목이 문서 인용하기 인쇄 / 내보내기 책 만들기PDF로 다운로드인쇄용 판 다른 언어 日 本 語 / 中 文 링크 편집 이 문서는 2019년 5월 11일 ( 토 ) 05 : 42에 마지막으로 편집되었습니다. 모든 문서는 크리에이티브 커먼즈 저작자표시 - 동일조건변경허락 3. 0에 따라 사용할 수 있으며, 추가적인 조건이 적용될 수 있습니다. 자세한 내용은 이용 약관을 참고하십시오. 미국 및 다른 국가에 등록되어 있는 Wikimedia Foundation, Inc. 소유의 등록 상표입니다. 개인정보 정책 위키백과 소개 면책 조항 개발자 쿠키 정책 모바일 보기
예를 들어 삽입 정렬의 실행 시간이 입력 크기에 따라 이차식으로 증가하기 때문에, 삽입 정렬은 O ( n2 ) 라 할 수 있다. Big O 표기법은 알고리즘의 최악의 경우 시나리오를 표현하는데 편리한 방법이며, 평균 경우를 표현 할 때도 활용 될 수 있다. 예를 들어 정렬의 최악의 경우 시나리오는 O ( n2 ) 이지만 평균 경우 실행 시간은 O ( n log n ) 이다. 실험적 증가 차수 [ 편집 ] 실행 시간이 t k na 다항식의 미적분 ( power rule ) 을 따른다고 가정하면, 실행시간 { t 1, t 2 } { displaystyle { t - { 1 }, t - { 2 } } } 과 문제 크기 { n 1, n 2 } { displaystyle { n - { 1 }, n - { 2 } } } 의 실험적 측정을 통하여 계수 a를 찾을 수 있다. [ 6 ] t 2 / t 1 = ( n 2 / n 1 ) a { displaystyle t - { 2 } / t - { 1 } = ( n - { 2 } / n - { 1 } ) ^ { a } } 이기 때문에 계수 a는 a = log ( t 2 / t 1 ) / log ( n 2 / n 1 ) {
n ) T 5 ( n 2 3 n ) ( n 1 ) T 4 T 1 T 2 T 3 T 7 k ( n 2 n ) k ( n 2 3 n ) k n 5 k = 2 k n 2 5 k n 5 k 2 k n 2 5 k n 2 5 k n 2 ( for n 1 ) = 12 k n 2 { displaystyle { begin { aligned } & T - { 6 } ( n ^ { 2 } n ) T - { 5 } ( n ^ { 2 } 3n ) ( n1 ) T - { 4 } T - { 1 } T - { 2 } T - { 3 } T - { 7 } leq k ( n ^ { 2 } n ) k ( n ^ { 2 } 3n ) kn5k = & 2kn ^ { 2 } 5kn5k leq 2kn ^ { 2 } 5kn ^ { 2 } 5kn ^ { 2 } ( { text { for } } n geq 1 ) = 12kn ^ { 2 } end { aligned } } } 그러므로 [ 1 2 ( n 2 n ) ] T 6 [ 1 2 ( n 2 3 n ) ] T 5 ( n 1 ) T 4 T 1 T 2 T 3 T 7 c n 2, n n 0
알고리즘 분석(영어: analysis of algorithms)은 컴퓨터 과학에서 알고리즘을 실행하는데 필요한 (시간과 기억 용량과 같은) 자원의 수를 결정하는 일을 가리킨다. 대부분의 알고리즘은 임의의 길이의 입력과 함께 동작하도록 구성된다. 일반적으로 알고리즘의 효율성과 실행 시간은 단계의 수 (시간 복잡도)와 기억 위치 (공간 복잡도)에 대한 입력 길이와 관련한 함수로 나타낼 수 있다. 알고리즘 분석이 더 광범위한 계산 복잡도 이론의 중요한 부분인데, 주어진 계산 문제를 해결하는 알고리즘에 필요한 자원에 대한 이론적 견적을 제공한다. 이러한 견적들은 효율적인 알고리즘을 검색하는데 도움을 준다. 알고리즘 분석에서는 보통 점근적(asymptotic) 의미로 복잡도를 계산한다. 즉, O표기법, Ω표기법, Θ표기법과 같은 방법으로 일정 크기의 입력 자료에 대한 복잡도 함수를 구한다. 예를 들어, 이진 탐색의 단계 수는 입력 자료의 크기에 대수적으로 비례하는데, 이것을 O (log ⁡ n) {\displaystyle O(\log n)} 또는 대수 시간이라 한다. 점근적인 방법을 사용하는 이유는, 같은 알고리즘이라도 입력 자료의 크기에 따라 수행 시간에 차이가 나는 것을 보완하기 위해서이다. 이런 수행 시간의 차이는 상수 배로 나타나는데, 이때의 상수를 숨은 상수(hidden constant)라고 한다. 시간 효율성의 추산은 수행 단계로서 정의하는 것에 의존한다. 의미있는 분석을 하려면, 각 단계에서 걸리는 수행 시간에 상한이 있어야 한다. 예를 들어, 두 수의 덧셈을 하나의 단계라 할 때, 각 수가 지극히 크면, 덧셈이 일정한 시간 내에 완료된다고 할 수 없기 때문이다. (2자리수의 덧셈을 하는 경우와 1000자리수의 덧셈을 하는 경우를 비교하여 생각해보라.)