내부 알고리즘

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "In-place 알고리즘" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2015년 1월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

컴퓨터 과학에서 내부 알고리즘은 보조 데이터 구조를 사용하지 않고 입력을 변환하는 알고리즘이다. 다만 보조변수에 대해서는 소량의 여분의 저장공간이 허용된다. 일반적으로 알고리즘이 실행될 때 출력에 의해 입력을 덮어쓴다. 내부 알고리즘은 요소 교체 또는 스와핑을 통해서만 입력 순서를 업데이트한다. 인플레이스되지 않은 알고리즘을 비플레이스 또는 아웃플레이스라고 부르기도 한다.

인플레이스는 약간 다른 의미를 가질 수 있다. 그것의 가장 엄격한 형태에서, 알고리즘은 함수 호출과 포인터를 포함한 모든 것을 세면서 일정한 양의 여분의 공간만 가질 수 있다. 그러나 단순히 길이가 n인 어레이에 대한 인덱스를 갖는 것은 O(log n) 비트를 필요로 하기 때문에 이 형식은 매우 제한적이다. 보다 광범위하게, in-place는 알고리즘이 입력을 조작하기 위해 여분의 공간을 사용하지 않고 작지만 일정하지 않은 여분의 공간을 필요로 할 수 있다는 것을 의미한다. 보통 이 공간은 O(log n)이지만, O(n)의 어떤 것이라도 허용될 때가 있다. 또한 공간 복잡성은 사용된 공간의 일부로 인덱스 길이를 계산할지 여부에 있어 다양한 선택권을 가지고 있다는 점에 유의하십시오. 종종 공간 복잡성은 길이를 무시한 채 필요한 지수나 포인터의 수로 주어진다. 이 글에서는 포인터 길이를 세면서 총 공간 복잡성(DSPACE)을 언급한다. 따라서 여기서 공간 요구사항은 지수와 포인터의 길이를 무시하는 분석에 비해 로그 n 인자가 더 많다.

알고리즘은 출력을 공간 사용의 일부로 계산하거나 계산하지 않을 수 있다. 인플레이스 알고리즘은 대개 출력으로 입력을 덮어쓰기 때문에 추가 공간이 필요하지 않다. 출력을 쓰기 전용 메모리나 스트림에 쓸 때는 알고리즘의 작업 공간만 고려하는 것이 더 적절할 수 있다. 로그 공간 감소와 같은 이론적 애플리케이션에서는 항상 출력 공간을 무시하는 것이 더 일반적이다(이 경우 출력이 쓰기 전용인 것이 더 필수적이다).

예

배열 지정 a 동일한 요소를 역순으로 보관하고 원본은 폐기하는 배열을 원한다고 가정합시다. 겉보기에는 간단해 보이는 한 가지 방법은 동일한 크기의 새 배열을 만들어 다음에서 가져온 복사본으로 채우는 것이다. a 적절한 순서로 그리고 나서 삭제한다. a.

 함수 역방향(a[0..n - 1]) 0 ~ n - 1 b[n - 1] := a[i] 리턴 b에 대해 b[0..n - 1] 할당 

유감스럽게도 이 경우 어레이를 보유하려면 O(n)의 추가 공간이 필요함 a 그리고 b 동시에 이용할 수 있는 또한, 할당과 할당 해제는 종종 느린 운영이다. 우리는 더 이상 필요하지 않기 때문에 a대신, 우리는 보조 변수에 대해 일정한 정수(2)만 필요한 이 인플레이스 알고리즘을 사용하여 그 자체의 반전으로 덮어쓸 수 있다. i 그리고 tmp, 배열이 아무리 크더라도.

 0부터 바닥((n-2)/2)까지 i에 대한 reverse_in_place(a[0..n-1) 함수 := a[i] a[i] := a[n - 1 - i] a[n - 1 - i] := tmp 

또 다른 예로, 버블 정렬, 빗 정렬, 선택 정렬, 삽입 정렬, 힙소트, 쉘 정렬 등 많은 정렬 알고리즘이 배열을 정렬된 순서대로 정렬된 상태로 재정렬한다. 이러한 알고리즘은 몇 개의 포인터만 필요로 하므로 공간 복잡성은 O(log n)이다.^[1]

Quicksort는 정렬할 데이터에 대해 인플레이스 방식으로 작동한다. 그러나 퀵소트는 분할 및 정복 전략에서 하위선을 추적하기 위해 O(log n) 스택 공간 포인터가 필요하다. 따라서 퀵소트에는 O(log² n)의 추가 공간이 필요하다. 이 일정하지 않은 공간은 기술적으로 내부 범주에서 퀵소트를 취하지만, 퀵소트 및 O(log n) 추가 포인터만 필요한 기타 알고리즘은 대개 내부 알고리즘으로 간주된다.

최종적이고 일정한 크기의 결과를 찾는 과정에서 입력 배열을 상당히 재정렬하는 경우도 있지만 대부분의 선택 알고리즘은 또한 제자리에 있다.

트림과 역방향과 같은 일부 텍스트 조작 알고리즘은 현장에서 수행될 수 있다.

계산 복잡성

계산 복잡성 이론에서, 내부 알고리즘의 엄격한 정의는 O(1) 공간 복잡성을 가진 모든 알고리즘, 즉 클래스 DSPACE(1)을 포함한다. 이 수업은 매우 제한적이다. 그것은 정규 언어와 같다.^[2] 사실 위에 열거한 예도 하나도 포함하지 않는다.

우리는 보통 O(log n)의 추가 공간이 필요한 문제의 등급인 L의 알고리즘을 제자리에 두는 것을 고려한다. 이 세분류는 포인터나 지수로 n 크기의 숫자를 허용하기 때문에 실제의 정의에 더 부합한다. 그러나 이러한 확대된 정의는 재귀적인 호출 때문에 퀵소트를 여전히 배제한다.

L로 그 저장하는 알고리즘을 식별하면, 몇가지 흥미로운 함의를 담고 있는 예를 들어,에(다소 복잡한)저장하는 알고리즘 경로 두 노드 사이에 무방향 graph,[3]에 존재하는 O(n) 여분의 공간depth-first 검색과 같은 전형적인 알고리즘을 사용하여 필요한 문제를 해결한 것(각각의 방문한 비트 n.시이 경우 그래프가 초당적인지 확인하거나 두 그래프에 연결된 구성 요소의 수가 동일한지 여부를 검정하는 등의 문제에 대한 알고리즘이 구현된다. 자세한 내용은 SL을 참조하십시오.

무작위성의 역할

많은 경우에 알고리즘의 공간 요구사항은 무작위화된 알고리즘을 사용하여 대폭 줄일 수 있다. 예를 들어, n 꼭지점 그래프에서 두 꼭지점이 그래프의 연결된 구성요소에 있는지 여부를 확인하려고 한다고 하자. 이것을 결정하는 것으로 알려진 단순하고 결정론적이며 내부 알고리즘은 없지만, 단순히 하나의 꼭지점에서 시작하여 약 20n계단의³ 무작위적인 산책을 수행한다면, 동일한 구성 요소에 있는 한 다른 꼭지점을 건너게 될 가능성은 매우 높다. 마찬가지로 Miller-Rabin primality test와 같은 소수성 테스트를 위한 단순 무작위화된 내부 알고리즘이 있으며, Pollard의 rho 알고리즘과 같은 단순 내부 무작위화된 인수 알고리즘도 있다. 이 현상에 대한 자세한 내용은 RL 및 BPL을 참조하십시오.

기능 프로그래밍에서

기능 프로그래밍 언어는 종종 데이터를 덮어쓰는 명시적인 내부 알고리즘을 지원하거나 지원하지 않는데, 이는 부작용의 한 유형이기 때문이다. 대신 새로운 데이터만 구성하도록 허용한다. 그러나, 좋은 기능 언어 컴파일러들은 종종 기존의 것과 매우 유사한 물체가 만들어지고 나서 오래된 물체가 버려지는 때를 인식하고 이것을 "후드 아래"의 단순한 돌연변이로 최적화할 것이다.

데이터를 수정하지 않는 내부 알고리즘을(데이터가 더 이상 사용되지 않는 경우는 제외) 신중하게 구성하는 것이 원칙적으로 가능하지만, 이는 실제로 거의 이루어지지 않는다는 점에 유의한다. 순수하게 기능적인 데이터 구조를 참조하십시오.

참고 항목

• 인플레이스 및 비플레이스 정렬 알고리즘 표

참조