不能分析此功能的运行时

Question

您好，我有这个问题，但我错了，我只是不明白这一点。 这是关于获得这个嵌套循环的确切运行时间。

具体而言，我可以理解，直到“对于i = 2，内部循环运行时间：2n-2”。然而，之后，我无法理解。

问题1）

首先，它说For i=n, inner loop runtime is n+1。但从我的角度来看，这没有任何意义。让我假设n = 3，当i = 3时，外循环执行其最后一个循环，然后j运行内循环3次（从3到5，因为j = 3 = n < 2 * n = 2 * 3 = 6）。但是，回答说inner loop runtime is n+1，如果我把3变成n+1它变成4倍。我不明白为什么这个答案是正确的。

问题2）

我怎样才能得到答案1.5n^2 + 0.5n从2n+(2n-1)+(2n-2)+...+(n+1)的最后形式？你能告诉我整个步骤如何在数学方面成为后者？具体关于如何2n + (2n-1) + (2n-2) + ... + (n+1)变成n*n + (1+2+3+...+n)？我认为公式n(n+1)/2在这里与n=(n+1)一起使用，但它不适用于我。

这里有什么公式吗？

Answer 1

问题1

你是正确的，对于第i个内部循环运行时应该是2N -i的，因此对于i = n，则内循环运行时应该是n。答案是错误的。

问题2

正确的答案应该是

2N +（2N-1）+ ... + N

你可以做的是你可以构造的另一总和序列

N +（N + 1）+ ... + 2n个

对于所有i = 0..n，你匹配2n-i和n + i因此，你有3n的（n + 1）项，所以2完全相同的序列的总和是3n（n + 1）因此，1个序列的总和为1.5N（N + 1）

您也可以直接套用公式为等差数列的总和，请参阅wiki页面 https://en.wikipedia.org/wiki/Arithmetic_progression