algorithm - c * c的时间复杂度？

Question

这里有时间复杂度问题：

for i = 1 to n
    if something
        p = p*c
    c = c*c

对于第 1 行，时间复杂度应该是 n，但是第 3 和第 4 行呢？那是n^2吗？还是n^n？

Answer 1

算术运算，如乘法，被考虑O(1)（常数时间），因此整个代码示例是O(n)，因为有n常数时间运算（O(1*n)）。

Answer 2

如果您正在分析 x 位整数，则乘法被视为常数时间。

如果您出于理论目的使用任意大整数进行分析，那么最著名的乘法算法是n*log(n)*2^Θ(log*(n)). 我不知道任何编译器会在任何机器上使用该算法进行乘法运算，因为实际上它比许多其他算法（不合理的大数字除外）慢得多，包括O(n²)您在 2 年级学习的标准乘法算法或3.