입력의 수에 다항식 인 입력의보다 강력한 인코딩을 기하 급수적으로 변할 수 있습니까?

Question

이것은 아마도 매우 기본적인 질문 일 것입니다. 그러나이 종류의 일이 대부분의 소개 알고리즘 과정에서 훑어 짐에 따라 결정적인 답변을 찾는 데 어려움을 겪고 있습니다. 입력 수에서 시간 다항식에서 실행되는 DFS와 같은 알고리즘을 가져옵니다. 이 경우 입력은 $ n $ 정점 및 $ m $ 모서리와 알고리즘을 가진 그래프입니다. $ o (m + n) $ 에서 실행됩니다.

그러나 실제로 런타임을 계산할 때 항상 바이너리 인코딩의 길이를 고려해야한다는 것을 알고 있습니다. 이것이 망명을위한 동적 프로그래밍 알고리즘과 같은 것이 실제로 다항식이 아닙니다.

DFS는 $ N + M $ "객체"를 입력으로 사용합니다. 각 객체가 고정 된 수의 비트 (예를 들어, 각 정점을 인코딩하는 데 1 비트가 걸리고 각 가장자리가 3 비트가 소요)를 취한 다음 알고리즘이 입력에서 실제로 다항식이라는 것을 이해합니다. 그러나 각 물체에 대해 고정 된 수의 비트가 필요한 이유가 있습니까? $ \ log (m + n) $ 비트를 취하는 입력의보다 강력한 인코딩이 존재할 수 있으며 갑자기 알고리즘 지수를 만듭니다.

실제 세계에서 실제적인 인코딩이 입력으로 주어진 모든 여분의 "객체"에 대해 고정 된 수의 비트 수를 필요로 할 것이라는 가정이있었습니다. 문자열 등; 따라서 이것은 런타임에 대해 생각하는 것이 가장 유용합니다. 그러나 나는 이것이 내 이해의 근본이라고 생각하기 때문에 확실하게하고 싶습니다. 미리 감사드립니다!

Answer 1

$ 2 ^ {n ^ 2} $ $ n $ 정점에서 지시 된 그래프로 표시됩니다. 따라서 이러한 그래프는 적어도 $ n ^ 2 $ 비트를 나타 내기 위해서는이를 나타냅니다. 따라서 항상 $ o (\ log n) $ 비트를 항상 사용하고 모든 그래프를 인코딩 할 수있는 인코딩 구성표에 대한 희망이 없습니다.

$ n $ 정점 및 $ m $ 가장자리로

에지에 초점을 맞추려는 경우 $ {n ^ 2 \ m} $ , $ m \ ll n ^ 2 $ 은 대략 $ (en ^ 2 / m) ^ m / \ sqrt {2 \ pi m / sqrt {2 \ pi m} $ 이므로 적어도 < SPAN 클래스="수학 용기"> $ M \ LG (n ^ 2 / m) + o (m) $ 비트가 모두를 나타냅니다. 이것이 $ \ omega (m) $ 이므로 $ o 만 사용하는 인코딩 체계에 대한 희망이 없습니다. (\ log m) $ 비트 (또는 $ o (\ log (m + n)) $ 비트)를 나타내며 모든 그래프를 나타낼 수 있습니다.

물론 로그 아웃 적으로 짧은 인코딩을 고려할 수는 있지만 모든 가능한 그래프의 작은 부분 만 표현할 수 있습니다. 예, 해당 방식으로 입력을 표현하고 이러한 그래프에서 도달 가능성 문제를 해결하려면 일반 DFS는 입력 크기에 시간을 기하 수 있습니다.

관련 : 간결한 데이터 구조