При обучении для экзамена в алгоритмах и структуры данных я наткнулся на вопрос, что это значит, если алгоритм имеет псевдо полином эффективности времени (анализ)псевдо Полином анализ алгоритмов
ли много поиска, но оказалось пустая передача
Это означает, что алгоритм является полиномиальным по размеру ввода, но вход фактически растет экспоненциально.
Например, возьмите проблему с суммой подмножества. У нас есть набор S из n целых чисел, и мы хотим найти подмножество, которое суммируется до t.
Для решения этой проблемы вы можете просто проверить сумму каждого подмножества, так что это O (P), где P - количество подмножеств. Однако на самом деле число подмножеств равно 2^n, поэтому алгоритм имеет экспоненциальную сложность.
Надеюсь, что это введение помогает понять статью википедии об этом http://en.wikipedia.org/wiki/Pseudo-polynomial_time :)