作者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