|
1.Give the order-of-Magnitude time efficiency (in THETA) 5 h6 ^, U A4 \0 T3 _ g: D
for the algorithm.
A: q& ?% _3 W, \4 Y D# w q - T7 h2 K7 b, m9 Q
Step 1:get values for D1, D2,,,,,, Dn
% p+ j, Q4 _; L, G' G5 c) L) X Step 2:get sum=0
5 G: J( I+ ]& C9 B2 j Step 3:set left=1 ' u$ G$ b$ G, z2 R( }+ J; s! q1 u
Step 4:repeat Step 5 to 7 until left>N
3 d/ Y# x' M* G Step 5: if Dleft is positive then
6 T! y9 z: D' ?+ s' v Step 6: set sum=sum+Dleft ) l- z, p/ x" ~( P$ r4 p3 U1 s
Step 7: set left=left+1 $ b- v; y+ W; ?9 M9 v4 |
Step 8: print out sum as the answer 5 u% R! n% H9 K3 h) l
( k, O+ T9 D0 D2 W4 a- @
# S% J( x0 d0 K5 \% U: a: b7 i6 U
1 p0 j! C9 Z$ I: ]8 f# U9 j0 O8 T
2.Give the order-of-magnitude time efficiency(in THETA) 8 y% y: z }# _
for the the algorithm.
3 a. I; X" d6 a: K
Q0 s* L- F0 q, `8 Y7 R Step 1:get values for L1, L2,….. Ln 9 t. b: f4 H: K7 z- [. A$ L" J% t& b
Step 2:set i=0
# h: F$ i" D( w3 ^* Y% H Step 3:repeat Steps 4 to 8 until i>N
0 t5 V( l' _- r Step 4: set j=1
8 d2 ~. s$ v' @2 C Step 5: repeat Steps 6 and 7 until j>N
7 @" I5 J6 y, }- N J Step 6: print(LI,Lj) 3 B# C' t# K- S ]
Step 7: add 1 to the value of j
$ o, z3 D7 I2 K* B& X7 w$ @ Step 8: add 1 to the value of i " `" O. h7 Z& _
" m0 L( o3 k4 ~
求以上二題的時間複雜度 |
|