範例9
The "Gauss Elimination with backward substitution" is used to solve
the n by n linear system (i.e.,Ax = b,A = [a_ij],x = [x_j] and b = [b_i]
1 ≦ i ≦ n,1 ≦ j ≦ n).
Please first list the algorithm,and then based on the complexity
analysis,determine the number of the multiplication/division and
addition/subtraction of this algorithm. If n is very large,what
order (the time complexity) do you conclude (i.e., O(n), O(2^n) or
O(n^3))?
Ans: Gauss Elimination algorithm 如下：
input n,[a_ij]
for k = 1,2,...,n-1 do
for i = k+1,k+2,...,n do
z ← a_ik/a_kk
a_ik ← 0
for j = k+1,k+2,...,n do
a_ij ← a_ij - z a_kj
end
end
end
output [a_ij]
我想請問範例9在P1-66的解答裡，為什麼
Gauss Elimination algorithm需要的乘/除法和加/減法數量會是：
n(2n-1)(n-1)
(n-1)^2 + (n-2)^2 + ‧‧‧ + 1^2 = ─────── 個乘法
6
n(n-1)
(n-1) + (n-2) + ‧‧‧ + 1 = ──── 個除法
2
n(2n-1)(n-1)
(n-1)^2 + (n-2)^2 + ‧‧‧ + 1^2 = ─────── 個加減法
6
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 211.74.179.135