作者peterpan126 (雲淡風輕)
看板Grad-ProbAsk
標題[問題] 程式執行次數
時間Fri Apr 24 15:06:46 2009
for i <- 1 to n do
j <- i
for k <- (j+1) to n do
x <- x+1
end
end
問這程式的執行次數為多少?
我一開始用直覺是認為 n平方 不過第二行有穿插 j <- i，該如何分析呢?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.116.5.37
1F：推 thank1984:外圈i=1 j=1, 內圈k=2 to n 所以執行n-1次 第二圈 04/24 15:33
2F：→ thank1984:k = 3 to n 執行 n-2次 n-3......1 所以為O(n^2) 04/24 15:35
3F：→ thank1984:有錯請指正 感謝 04/24 15:35
4F：推 nowar100:我想的同1樓 O(n)+O(n-1)+...+O(2)+O(1) => O(n^2) 04/24 19:12
5F：→ nowar100:不過我不確定 還沒念 XD 04/24 19:12
6F：→ peterpan126:我一開始也是認為是n^2 不過怕有異! 04/24 20:32
7F：推 thank1984:如果是問次數那就寫 [(n-2+1)*(n-2)]/2 04/24 23:03