如何找到乘以 i 的语句的时间复杂度

Question

我是一名学生，正在尝试分析以下伪代码片段的时间复杂度

function stars(A):
    for i in [1:n]:
        print ’*’ i many times

这个的时间复杂度不应该是O(n)吗？只有 1 个 'for' 循环。它的解决方案说它的 O(n^2).

Answer 1

我怀疑你的伪代码

print ’*’ i many times

表示代码执行了一个额外的循环。这意味着给定 n 你在 [0, n] 中每次出现时打印 n 次。因此 n * n 给你结果 O(n^2).