c - 只有 O(n) 的嵌套 for 循环

Question

我将如何编写一个包含嵌套 for 循环但只有 order(n) 的函数？我不确定我是否需要使用递归。

Answer 1

如果内部 for 循环是恒定数量的循环而不是可变数量的循环，而外部循环是可变数量的循环（反之亦然），则时间复杂度为 O(n*C)，其中 C 是常数，这只是意味着 O(n) （因为大 O 表示法只与增长因素有关）。