迭代 n 个重复数字的函数的时间复杂度

Question

假设我有一个函数

def f(n):

   for x in range(int("1" * n)):
       ....  # assume this step is o(1)

这个函数接受一个整数 n 然后迭代 1 重复 n 次。

示例。

对于 n = 5

for i in range(11111): 
    pass
   

对于 n = 4

for i in range(1111):
    pass

这个函数的输入 n 的时间复杂度是多少，或者你会如何计算它？

如果问题不清楚，我们深表歉意，感谢您的帮助。

Answer 1

给定输入值 n，迭代次数将为 (10^n - 1)/9。
因此，每增加一次输入，迭代次数就会增加 10 倍。

另请注意，n 不是输入大小，而是输入的值，因此时间复杂度是双指数的，因为输入大小是 n 中的对数。