找出最坏情况下输出“Hello”的次数

Question

我上周在一个测验中有这个问题，我不明白我们是如何解决它的。这是一个问题（见附件）。由于有嵌套for循环，我看到n ^ 2来自哪里，但我不确定-n和* .5在答案中的来源。

Answer 1

“最坏的情况”（如果你可以称打印很多hellos为“最糟糕”的情况......）是当A全为零（例如）时，所有<= evaluate to true。但是这个循环运行了多少次？它不是n ^ 2：它不是n + n + n + n n次......看看内循环！它不是从1到n-1，而是从1到i。所以打印输出的数量是1 + 2 + 3 + ... +（n-1）。并且这恰好是n *（n-1）/ 2，即（n ^ 2-n）/ 2。这很容易证明（高斯这样做是一个小男孩:-)），但由于这是一个多选题，你可以测试一个n。

如果你很好奇如何证明X = 1 + 2 + 3 + ... +（n-1）是n *（n-1）/ 2，这里是高斯的诀窍：按不同的顺序写两次X：

X = 1     +    2  +     3 + ... + (n-1)
X = (n-1) + (n-2) + (n-3) + ... + 1

现在总结两个X的。注意在每列中你有两个数字，总计n - 1+（n-1）是n，2 +（n-2）是n，依此类推。所以基本上整个总和都有n-1份n。所以

2*X = n * (n-1)

所以X = n *（n-1）/ 2

这正是您要解释的（n ^ 2-n）* 0.5。