8 1 Gaussian Elimination - Amount of Computation >运算量/* Amount of Computation 由于计算机中乘除/ multiplications/divisions*运算的时 间远远超过加减/ additions/ subtractions运算的时间,故 估计某种算法的运算量时,往往只估计乘除的次数,而且通 常以乘除次数的最高次幂为运算量的数量级。 6 Gaussian elimination: (n-k)次 Step k:识 Gaussian elimination的总乘除次数为(m-6)(m-k+2)次 运算量为"级。 消元乘除次数: 共进行 ∑(n-kn-k+2 x=b/a (n-澡除次数 -一 n-,…)1+∑(m-i+1)=+ 2➢ 运算量 /* Amount of Computation */ §1 Gaussian Elimination – Amount of Computation 由于计算机中乘除 /* multiplications / divisions */ 运算的时 间远远超过加减 /* additions / subtractions */ 运算的时间，故 估计某种算法的运算量时，往往只估计乘除的次数，而且通 常以乘除次数的最高次幂为运算量的数量级。  Gaussian Elimination: Step k：设 ，计算因子 且计算 0 ( )  k akk / ( 1, ..., ) ( ) ( ) m a a i k n k kk k ik = ik = + ( , 1, ..., ) ( 1) ( ) ( ) ( 1) ( ) ( ) i j k n b b m b a a m a k ik k k i k i k ik kj k ij k ij = +    = − = − + + 共进行n − 1步               =                           ( ) (2) 2 (1) 1 2 1 ( ) (2) 2 (2) 22 (1) 1 (1) 12 (1) 11 . . . . . . . . . ... ... ... n n n n nn n n b b b x x x a a a a a a ( ) ( ) / n nn n xn = bn a ( 1, ..., 1) ( ) 1 ( ) ( ) = − − = = + i n a b a x x i ii n j i j i ij i i i ((n n −−kk)) 2次次 (n − k) (n − k + 2) 次 n n n n k n k n k 6 5 3 2 ( )( 2) 3 2 1 1 = + −  − − + − = 消元乘除次数： (1 n 次− i +1) 次 2 2 1 ( 1) 1 2 1 n n n i n i + − + = + − = 回代乘除次数： Gaussian Elimination 的总乘除次数为 n n ，运算量为 级。 n 3 1 3 2 3 + − 3 3 n