3
알고리즘의 입력 크기가 2^n이고 알고리즘이 $ O (n2^n) $ time에서 실행되는 경우. 이 경우 알고리즘은 입력 크기와 관련하여 다항식 시간으로 실행된다고 말할 수 있습니까?다항식 시간 알고리즘입니까
알고리즘의 입력 크기가 2^n이고 알고리즘이 $ O (n2^n) $ time에서 실행되는 경우. 이 경우 알고리즘은 입력 크기와 관련하여 다항식 시간으로 실행된다고 말할 수 있습니까?다항식 시간 알고리즘입니까
예, O (k log k) 시간 알고리즘입니다 (k = 2^n).
감사합니다. @ David 따라서 다항식 시간 또는 의사 다항식이라고 말할 수 있습니까? 나는이 두 가지를 혼동합니다. –
좋은 질문과 좋은 대답 - 모든 것은 올바른 정의에 달려 있습니다. 예를 들어, 행렬 곱셈 알고리즘의 경우, 런타임 경계는 대개 'n * n'크기의 입력이있는 'n'이라는 용어로 표현됩니다. – Codor
@NARAYANCHANGDER Polynomial. 의사 다항식 실행 시간의 예는 O (k^log k)이다. –