发现涉及实数乘法的大哦

Question

我有以下家庭作业问题：

𝑛度多项式𝑝（𝑥）是形式为的方程：

[其中𝑥是一个实数，每个𝑎𝑖是一个实常数，𝑎𝑛≠0。描述一个简单的𝑂（𝑛^ 2）-时间方法，计算𝑝（𝑥）的特定值。验证运行时。

所以我的问题是：因为ai可以是任何实数，所以甚至可以保证O（n ^ 2）运行时，并且当它接近无穷大时，运行时也可以。

这是我到目前为止输入的内容：

“由于最快的乘法知道算法（Harvey-Hoeven算法）花费Θ（nlogn）时间（其中n是每个要乘的数字的位数），并且由于ai可以是任何实数，所以存在无法保证O（n ^ 2）时间。这是因为，如果任何一个常数ai都大于例如n ^ 2个数字，那么单次乘法将至少花费（nlogn）^ 2时间。”

如果不是这样，我在哪里出错了？

Answer 1

具有许多复杂性理论的问题，其中“运行时间”是以（通常未指定的）抽象单位来衡量的，这可能与真实计算机上的挂墙时间不符。在这里，我想问这个问题的人意味着运行时是“算术运算”。尽管不清楚，因为没有明显的算法可以在O（n ^ 2）算术运算中运行，而在o（n ^ 2）中也不是。

您的答案是正确的，如果您假设使用“位复杂度模型”，尽管通常在这种情况下，“ n”将是输入的大小，而不是求和的极限，并且如何表示实数的细节将是变得重要。

Answer 2

可能有两种情况：

情况1：如果n接近无穷大，则您的观点是正确的。

情况2：如果n是不接近无穷大的实数，则计算将涉及n个加法运算（a0 + a1 + a2 + a3 + .... + an）。

假定某个整数的最大长度，ai等于某个常数m，则总时间复杂度将为O(n * m)。