|
1.Give the order-of-Magnitude time efficiency (in THETA)
* }( k9 P* b9 y+ S for the algorithm. 0 ~) W) G" h! q5 m# `" x6 [1 r9 o
) Z8 }: J) i$ _/ {7 i; b Step 1:get values for D1, D2,,,,,, Dn
: Z- _& X2 a6 @6 Y* g Step 2:get sum=0
+ p+ A5 O' |# q& w1 q2 {8 O" _7 } Step 3:set left=1 1 t5 p6 T; y/ |3 F' T
Step 4:repeat Step 5 to 7 until left>N $ G( v- H" J8 X* h' v" z
Step 5: if Dleft is positive then % S1 A# V$ q) T9 d; J* O% y
Step 6: set sum=sum+Dleft 2 d: \% O; K5 O- A9 C' p. P% t7 s
Step 7: set left=left+1
+ `& U3 t% L8 B0 x; |2 Q Step 8: print out sum as the answer
! A. t) X- c/ I( f" t; M/ J `5 c' Z# g5 i8 ~$ Y
2 A Y) \. U: ~$ e4 b: |
* G& Z$ v$ \5 h% ~5 P( s' V
2.Give the order-of-magnitude time efficiency(in THETA)
' l/ }- u& q' o# [! R for the the algorithm. 6 u: [0 @+ m' v3 ~* i
: t" t% ]( i7 R, X. E) K# n Step 1:get values for L1, L2,….. Ln 5 w9 z; \+ F( t' [
Step 2:set i=0
C! z4 V+ i. e Step 3:repeat Steps 4 to 8 until i>N
3 r' @, I- S+ v4 P& ^! ? Step 4: set j=1 ( e1 k5 C. M W [9 C
Step 5: repeat Steps 6 and 7 until j>N - i' ?8 N% ^( d% g- G T8 \# D
Step 6: print(LI,Lj)
& D( [5 U+ N8 d$ j Step 7: add 1 to the value of j
# l A: a8 ]! z+ ? Step 8: add 1 to the value of i
/ H7 a6 j. Z1 _% u" z- g$ G! Z
. w( ^ m; n" |2 Q9 S1 V求以上二題的時間複雜度 |
|