0
Дайте алгоритм, который вычисляет входной полиномСложность времени для функции полинома?
п х п + а п-1 х п-1 + ⋯ + а х + а
Для заданного значения x во времени Ω (n) и O (n).
Я пытался доказать это, но не смог найти подходящий алгоритм, может ли кто-нибудь помочь мне получить эту идею?
Как это возможно быть n^2? Существует n + 1 членов, каждый из которых вычисляется в O (1) раз, с дополнениями n O (1). – Adam
@Adam: вы не можете вычислить x^n в O (1). –
Вы считаете, что числа являются большими целями с произвольным размером? Если они фиксированы, это «O (N)». – usr