비 모노톤 최악의 경우의 복잡도에 대한 예

Question

누군가가 모노톤이 아닌 최악의 경우의 행동을하는 자연스러운 프로그램이나 알고리즘을 알고 있습니까?

비 모노톤 최악의 경우의 동작은 크기 n + 1의 입력에 대한 최악의 경우의 런타임이 크기 n의 입력에 대한 최악의 경우 런타임보다 적어지는 자연수 n이 있음을 의미합니다.

물론이 동작으로 프로그램을 구성하는 것은 쉽습니다. 자연스러운 프로그램에서 작은 n (n = 1과 같은)에 대해서도 이런 경우가 발생할 수 있습니다. 하지만 큰 n에 대해 비 모노톤 (non-monotone) 인 유용한 알고리즘에 관심이 있습니다.

Answer 1

누가 자연스러운 프로그램이나 알고리즘을 알고 있습니까? 비 - 모노톤 최악의 경우?

"자연 프로그램 또는 알고리즘"을 정의하십시오. 개념 "알고리즘"은 내가 알고있는 정의를 가지고 있으며, 단조롭지 않은 최악의 경우의 런타임 복잡성을 가진 알고리즘이 있습니다 (올바르게 인정하는 것처럼). 불필요한 작업을하지 않거나 해결할 문제의 클래스에 대한 런타임 복잡성이 최소화되면 프로그램이 "자연스럽지"않은 것입니까? 이 경우 BubbleSort가 알고리즘이 아니라고 주장 하시겠습니까? 더 중요한 것은, 가장 단순한 문제가 아닌 가장 단순한 문제를 정의 할 수 있다는 것입니다. 그런 문제가 "부자연 스럽습니까"? "자연적 문제"에 대한 당신의 정의는 무엇입니까?

물론이 동작으로 프로그램을 구성하는 것은 쉽습니다.

그럼 실제 질문은 무엇입니까? 자연/유용한 알고리즘 및 문제에 대한 정의를 내릴 때까지 질문에 답할 수 없습니다. 사람들이 이미 실제 세계에서 사용하고있는 기존 알고리즘에만 관심이 있습니까? 그렇다면 그 사실을 진술해야하며 문제는 문헌을 찾는 것 중 하나가됩니다. 솔직하게 말하면, "자연적이고 유용한 알고리즘"의 합리적인 정의를 상상할 수는 없으며, 이는 non-monotone 런타임 복잡도를 가진 알고리즘의 많은 예제를 배제 할 것입니다. ...

그러나 유용한 알고리즘은 유용하지 않습니다. 모노톤 for 큰 n.

"유용한 알고리즘"을 정의하십시오. 개념 "알고리즘"은 내가 알고있는 정의를 가지고 있으며, 단조롭지 않은 최악의 경우의 런타임 복잡성을 가진 알고리즘이 있습니다 (올바르게 인정하는 것처럼). 알고리즘이 문제를 올바르게 해결하면 알고리즘이 "유용"합니까? 비 단조로운 런타임 복잡성을 가진 알고리즘으로 해결할 수있는 문제를 쉽게 정의 할 수 있습니다.

Answer 2

이진 검색에 대해 생각해보십시오.

바이너리 검색을 구현할 때 분할하려는 배열 세그먼트가 홀수 인 경우를 생각해 볼 필요가 있습니다. 이 시점에서 두 가지 선택 사항이 있습니다. 1. 반올림/올림 2. 계속 진행하기 전에 두 색인을 모두 확인하고 결정하십시오.

첫 번째 경우를 선택하는 경우 (반올림한다고 가정합니다). 검색하려는 숫자가 중간 지점을 통과 한 홀수 길이의 배열의 경우 추가 반복이 필요합니다.
이상한 배열에 요소가 하나 더 추가되면 여분의 반복을 절약 할 수 있습니다.

두 번째 경우에는 더 많은 홀수 반복을 사용하는 알고리즘의 대부분의 실행이 추가 요소와 함께 사용 된 경우 더 많은 비교가 필요합니다.

이 모든 것은 구현에 따라 크게 다르므로 실제 알고리즘이 없으면 실제 응답이 될 수 없다는 점에 유의하십시오.

또한이 모든 내용은 실제 런타임 diff와 비상용 diff가 아니라는 가정하에 작성되었습니다. 그렇지 않은 경우 대답은 '아니요'입니다. 비 단조로운 최악의 경우 알고리즘 점근선 실행 시간이있는 알고리즘이 없습니다. 그것은 "최악의 경우"의 개념에 어긋납니다.