Pseudopolynom von konstanten Zeiten

Question

Pseudopolynom bedeutet, dass es in Bezug auf die Größe der Eingabe polynomial ist, aber in Bezug auf die Größe der Eingabe exponentiell ist. Im Rucksack wird O (nW) als Pseudopolynom angesehen. Ich habe einige Leute gesehen, die nx oder ny nennen, so ziemlich alles mit n, Pseudopolynom, denn wenn n groß wird, betrachten sie ns Bitlänge mehr. Also ist es wahr, dass alles mit einer Variable, die mit ihrer Größe als Polynom betrachtet werden kann, tatsächlich Pseudopolynomial ist?

Answer 1

Wenn Sie Ihre Eingabe eine einzelne Zahl, wie "is the number x a prime number" ist, dann O(x) (oder O(sqrt(x)) pseudo Polynom - die Eingangsgröße ist O(logx) in diesem Fall Polynom so in x nicht Polynom in der Eingangsgröße bedeutet

. Wenn Ihre Eingabe jedoch ein Array mit n Elementen ist, dann ist die Eingangslänge selbst linear in n, und O(n) bedeutet Polynom und nicht Pseudopolynom