如何导出该算法的大O

Question

这是算法：

for i ← 1 to n by 1 do
for j ← 1 to i by 1 do
for k ← 1 to j by 1 do
x = x + 1
end
end
end

内部循环的迭代次数取决于外部循环。。。那么，如何推导时间复杂性呢？

Answer 1

此算法随着第^个四面体数的增加而增加。这是因为循环可以被视为一个范围内的总和：

• 外环：∑₌₁
• 中间回路：∑^₌₁
• 内环：∑_<1>
• 内部语句：在恒定时间内运行，因此算作1次操作

这意味着内部语句多次运行：

∑_<1>(∑_sub=1<1)>

内部总和真的是，所以我们可以写：

∑_<1>

我们将这个表达式识别为四面体数(参见上面维基百科链接中的公式)

这个双和是(+1)(+2)/6=θ(³)

另一种方法是，循环导致、和的组合，它们以非递减顺序出现。因此，执行x = x + 1的次数与我们可以从范围1...中选择三个值的多集的方式的数量相对应，允许重复。这个数字是"；多选择器3〃，这导致了相同的公式。