algorithm - 我的打印三角形算法的时间复杂度是多少？

Question

我的打印三角形算法的时间复杂度是多少？

void print(int n) {
    if (n < 0) return;
    for (int k = n; k > 0; k--) {
        out.printf("[*]");
    }
    out.println();
    print(--n);
}

我认为它是 O(n^2)，因为我们遍历了所有的列和行。我对吗？但是，我对递归对算法的影响有些怀疑。

Answer 1

第一次迭代有 n 个步骤，第二个 n - 1，依此类推直到 1。您还记得，序列 {1, 2 , …, n} 是 (n² + n)/2。 (证明是对归纳概念的标准介绍。)这确实是 O(n²)。