동적 문제(알고리즘)
Dynamic problem (algorithms)계산 복잡성 이론의 동적 문제들은 입력 데이터의 변화 측면에서 언급된 문제들이다.가장 일반적인 형태에서 이 범주의 문제는 대개 다음과 같이 명시된다.
- 입력 객체 클래스가 지정되면 입력 데이터를 수정할 때마다 입력 객체 집합에 대한 특정 질의에 응답할 수 있는 효율적인 알고리즘과 데이터 구조를 찾으십시오. 즉, 객체를 삽입하거나 삭제하는 경우.
이 세분류의 문제에는 다음과 같은 복잡성 측도가 있다.
- 공간 – 데이터 구조를 저장하는 데 필요한 메모리 공간
- 초기화 시간 – 데이터 구조의 초기 구축에 필요한 시간
- 삽입 시간 – 입력 요소를 하나 더 추가할 때 데이터 구조 업데이트에 필요한 시간
- 삭제 시간 – 입력 요소를 삭제할 때 데이터 구조 업데이트에 필요한 시간
- 쿼리 시간 – 쿼리에 응답하는 데 필요한 시간
- 해당 문제와 관련된 기타 작업
동적 문제에 대한 전체 연산 집합을 동적 알고리즘이라고 한다.
고정 입력 데이터의 관점에서 기술된 많은 알고리즘 문제(이 맥락에서 정적 문제라고 하며 정적 알고리즘에 의해 해결됨)는 의미 있는 동적 버전을 가지고 있다.
특례
증분 알고리즘 또는 온라인 알고리즘은 요소의 추가만 허용되는 알고리즘으로, 빈 입력 데이터에서 시작할 수 있다.
노쇠 알고리즘은 전체 데이터 구조의 초기화를 시작으로 요소의 삭제만 허용하는 알고리즘이다.
추가와 삭제가 모두 허용되는 경우 알고리즘을 완전 동적(full dynamic)이라고 부르기도 한다.
예
최대 원소
- 정적 문제
- N개의 숫자 세트는 최대값을 구한다.
그 문제는 O(N)시에 해결될 수 있다.
- 동적 문제
- 초기 N개 숫자의 경우 삽입 및 삭제가 허용되는 경우 최대값을 동적으로 유지하십시오.
이 문제에 대해 잘 알려진 해결책은 자가 균형 이진 검색 트리를 사용하는 것이다.공간 O(N)를 차지하며, 초기에는 O(N 로그 N)로 구성될 수 있으며, 삽입, 삭제 및 질의 시간을 O(로그 N)로 제공한다.
그래프
그래프의 가장자리 삽입 및 삭제가 허용되는 경우, 연결성, 최대도, 최단 경로 등 그래프의 매개변수를 유지하십시오.[1]
