算法频率计数

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

我还想知道，一般来说，如何确定所有算法的频率计数，而不仅仅是这个算法。

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

目前还没有一种通用的计算运行时间的方法，如果有方法的话，复杂性理论就应该从计算机科学中删除。

Answer 2

好吧，让我们从内到外建立这个。

每次运行内环时，代码行都执行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时间。

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

虽然这个问题在一般情况下是无法判定的--如果您知道程序中每一行代码将执行多少次，那么您就解决了停止问题。