7
바보 같은 질문에 사과드립니다. 나는 내 기억을 조깅 할 수 없으며 인터넷 검색으로이 질문에 답하는 데 도움이되지 못했다.은 다항식으로 간주되는 O (| E | * | V |) 복잡도입니까?
기본적으로 그래프 G (V, E)가 주어진다면 O (| V |^2) 또는 O (| E |^2 + | V |^2)가 다항식 복잡성으로 간주되므로 O (| E | * | V |) 다항식도 마찬가지입니까? 그렇지 않다면 어떤 종류의 복잡성입니까? 나는 의사 다항식이 아니라고 믿는다.
또 다른 질문은 다음과 같습니다. O (m * n)은 다항식으로 간주됩니까? m과 n은 문제에 대한 두 개의 독립 입력 값입니다. 여기서 다항식 시간의 개념을 명확히하고 O (m * n)이 복잡성 유형에 대해 다른 이름을 갖고 있는지 알고 싶습니다.
오 그래. Boo me :) 어떻게 볼 수 없습니까? 또 다른 질문은 다음과 같습니다. O (m * n) 다항식입니까? m과 n은 문제에 대한 두 입력의 크기입니까? 여기서 다항식 시간의 개념을 명확히하고 싶습니다. – Simo
@Simo, 후속 질문을 이해할 수 없습니다. 명암 대비를위한 의사 다항식의 예제가 필요하다면, 다음을보십시오 : http://stackoverflow.com/questions/4538581/why-is-the-knapsack-problem-pseudo-polynomial –
차이점은 다음과 같은 의사 다항식 복잡성입니다. 이 경우는 용량 (즉, 오른손 크기)에 따라 다르며이 값은 현저하게 커질 수 있습니다. –