算法的频率统计

Question

我需要知道如何确定以下程序中sum:= sum+1语句的频率计数：

sum:=0

for i:=1 to n do
  for j:=1 to i do
    for k:=1 to j do
        sum:= sum+1
    end<br/>
  end
end

我想了解如何确定所有算法的频率计数，而不仅仅是特定算法。

- Brendan

---

运行程序并检查sum的值？ - Anon.

这与遗传算法有什么关系？ - Joey Adams

抱歉，我以为它说的是通用算法...已经修复了。 - Brendan

尝试找到“sum”最终值的公式。 - ruslik

Answer 1

∑∑∑ 1 = ∑∑ j = ∑ (i*(i+1))/2 = ∑(i^2+i)/2 = (n(n+1)(2n+1)/6+n(n+1)/2)/2 = n(n+1)(n+2)/6

这是您的公式：

F(n) = n(n+1)(n+2)/6

目前并没有一种通用的方式来计算运行时间，如果有的话，复杂性理论应该被移除计算机科学。

- Saeed Amiri

---

非常感谢。我已经找到了答案，但这正是我采取的完全相同的方法，所以我会将其标记为答案。感谢您的帮助。 - Brendan

Answer 2

对于表示精确频率的表达式，您需要参考多项式求和公式。

也就是说，内部循环取决于外部循环的当前迭代。例如：

sum := 0
for i:=1 to n do
  for j:=1 to i do
    sum := sum + 1

根据变量n，总和为1+2+3+4+5+...+n。在求和表示法中，它为Σ_i=1ⁿi。

- Joey Adams

---

例如，如果n为200，频率计数和sum的值会是多少？ - Brendan

如果您想要一个特定的解决方案，而不是一个通用公式，为什么不运行程序并查看总和呢？ - Christian Severin

Answer 3

好的，让我们从内到外构建它。

每次内部循环运行时，该行代码会执行j次。 到目前为止一切顺利。

因此，每次运行中间循环时，我们会执行语句1 + 2 + 3 + ... + i-1 + i i *（i + 1）/ 2或（i ^ 2 + i）/ 2。

对于每次我们运行外部循环，我们会执行语句((1 ^ 2 + 1) + (2 ^ 2 + 2) + ...（n ^ 2 + n））/ 2次。

我将把最终结果留给读者作为练习。

尽管通常情况下这个问题是不可判定的 - 如果您知道程序中每行代码将执行多少次，则已经解决了停机问题。

- Anon.