不能分析此功能的運行時

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