慕運(yùn)維8079593
2021-11-24 15:45:07
// For the below algorithm, calculate the exact number of times // System.out.println statement is executed as a function of n. Assume n≥1 for (int i=0; i<=n; i++) { for (int j = i; j < 2*n; j++) { System.out. println(”1 iteration executed!”); } }這是解決方案,但我很難理解數(shù)學(xué)。Overall RT = 2n + (2n-1) + (2n-2) + … + n = = (n+1)*n + (n+(n-1)+(n-2)+…+1+0) = = n2 + n + n*(n+1)/2 = = 1.5*n2 + 1.5n
2 回答

蝴蝶不菲
TA貢獻(xiàn)1810條經(jīng)驗(yàn) 獲得超4個贊
循環(huán)在第一次迭代中運(yùn)行 2n 次,然后每次減少 1 次,直到它運(yùn)行時的第 (n+1) 次迭代n
。
2n + (2n-1) + (2n-2) + … + n
請注意,n+1
該系列中有術(shù)語。
讓我們n
從每個術(shù)語中減去并分別添加它們。這給我們(n+1)*n
加上每一項(xiàng)減去 n:
(n+1)*n + (2n-n) + (2n-1-n) + … + (n-n)
這簡化為:
(n+1)*n + n + (n-1) + (n-2) + … + 0
現(xiàn)在,眾所周知, 的總和1+2+3+...+n
是(n+1)*n/2
,而這正是n + (n-1) + (n-2) + … + 0
:
(n+1)*n + (n+1)*n/2
現(xiàn)在我們可以將它相乘:
n^2 + n + (n^2)/2 + n/2
這簡化為:
1.5n^2 + 1.5n

哈士奇WWW
TA貢獻(xiàn)1799條經(jīng)驗(yàn) 獲得超6個贊
所以讓我們一步一步來。假設(shè) n 的值為 4。
i
開始于0
soj
也開始在0
這個時間j
增量直到 1 小于2*n
8
這意味著j
這個時間的值將是0, 1, 2, 3, 4, 5, 6, 7
,總共 8 個不同的值
i
增量1
所以j
在開始1
這段時間j
仍然將遞增,直到1小于2*n
或8
的值j
,這一次將是1, 2, 3, 4, 5, 6, 7
,共7個不同的值。比上次少了1!
下一次, 的值j
將為2, 3, 4, 5, 6, 7
。6 個不同的值。
這種模式將一直持續(xù)到j
開始4
。然后j
將采用 4 個不同的值,循環(huán)將退出。
添加回答
舉報
0/150
提交
取消