출력 민감 알고리즘

컴퓨터 과학에서 출력에 민감한 알고리즘은 입력의 크기 대신에 또는 입력의 크기 외에 출력 크기에 따라 실행 시간이 달라지는 알고리즘이다.예를 들어 입력 크기의 선형에서 입력 크기의 2차까지 출력 크기가 매우 다양한 특정 문제에 대해 출력 크기를 명시적으로 고려하는 분석은 동일한 점증상 복잡성을 가질 수 있는 알고리즘을 구별하는 더 나은 런타임 한계를 생성할 수 있다.

예

뺄셈에 의한 분할

출력 민감 알고리즘의 간단한 예는 다음과 같은 추가, 뺄셈, 비교만을 사용하여 두 개의 양의 정수를 나눈 값과 나머지 값을 계산하는 뺄셈에 의해 분할 알고리즘 분할에 의해 주어진다.

반항하다 나누다(번호를 붙이다: 인트로, 분열시키다: 인트로) -> 투플레[인트로, 인트로]:     """뺄셈으로 나눈다."""     만일 아닌 분열시키다:         높이다 ZeroDivisionError     만일 번호를 붙이다 < 1 또는 분열시키다 < 1:         높이다 ValueError(             f"양수 정수만 "             f"dividend( (){번호를 붙이다}) 및 divisor ({분열시키다})."         )     q = 0     r = 번호를 붙이다     하는 동안에 r >= 분열시키다:         q += 1         r -= 분열시키다     돌아오다 q, r 

출력 예:

>>>나누다(10, 2) (5, 0) >>>나누다(10, 3) (3, 1) 

이 알고리즘은 θ(Q) 시간이 걸리기 때문에 Q 지수가 작다고 알려진 시나리오에서는 빠를 수 있다.다만 Q가 큰 경우 롱 디비전 등 더 복잡한 알고리즘에 비해 월등히 우수하다.

연산 기하학

평면 내 유한한 점 집합의 볼록한 선체를 찾기 위한 볼록 선체 알고리즘은 n 점에 대해 Ω(n log n) 시간이 필요하다. Graham 스캔과 같은 비교적 간단한 알고리즘도 이 하한을 달성한다.볼록 선체가 모든 n 점을 사용할 경우 이것이 우리가 할 수 있는 최선이다. 그러나 많은 실제 지점들, 특히 무작위 지점들의 경우 볼록 선체에 있는 h 지점의 수는 일반적으로 n보다 훨씬 작다.따라서 O(n log h) 시간만 필요한 최종 볼록 선체 알고리즘과 Chan의 알고리즘과 같은 출력에 민감한 알고리즘은 그러한 포인트 집합에서 상당히 더 빠르다.

출력 민감 알고리즘은 컴퓨터 기하학 애플리케이션에서 자주 발생하며, 숨겨진 표면 제거^[1] 및 라우터 테이블의 범위 필터 충돌 해결과 같은 문제에 대해 설명되어 왔다.^[2]

프랭크 닐슨은 그룹화 및 쿼리라고 알려진 출력 민감 알고리즘의 일반적인 패러다임을 설명하고 보로노이 다이어그램의 셀 계산을 위한 알고리즘을 제공한다.^[3]Nielsen은 이러한 알고리즘을 두 단계로 세분화한다: 출력 크기를 추정하는 것과 최종 솔루션을 구축하기 위해 쿼리된 추정치에 근거한 데이터 구조를 구축한다.

일반화

보다 일반적인 종류의 출력에 민감한 알고리즘은 문제에 대한 솔루션 집합을 열거하는 열거 알고리즘이다.이러한 맥락에서 알고리즘의 성능은 출력에 민감한 방법으로도 측정되며, 예를 들어, 두 가지 연속적인 솔루션 사이의 지연을 경계한다.

참고 항목

• 게으른 평가

참조