|
1.Give the order-of-Magnitude time efficiency (in THETA)
' w* |5 t, I( J. v+ m/ s6 d: j for the algorithm. ( [. n, t( B! [. w5 T0 Y
/ W; r: W! I" R$ C: G
Step 1:get values for D1, D2,,,,,, Dn
- z3 b" e4 A# J4 h1 Z Step 2:get sum=0 6 R. c$ S: t) E, E
Step 3:set left=1
; {* [ f) j4 ^9 W Step 4:repeat Step 5 to 7 until left>N 1 B! h" t! C8 k" h, i7 P, c! M- @+ A
Step 5: if Dleft is positive then
4 [( l4 V1 ?* S' d7 i q3 L Step 6: set sum=sum+Dleft
/ ^( ^0 H1 N) n9 q2 Z, { Step 7: set left=left+1 9 B! h- w$ i) ?9 A" N" E* z2 o- h
Step 8: print out sum as the answer 1 P$ @! S( P$ l
' X, F5 ]: Z; A# r* `: K9 b# a* n9 e2 M7 F2 ?6 d! \
' |/ k; K) E& `2 }/ M, s2.Give the order-of-magnitude time efficiency(in THETA)
" q; d- P% i5 B. L) I5 \ for the the algorithm. " v6 x" ~ @ t; E7 S
; u( q! |2 }2 I V L* d% v$ \ Step 1:get values for L1, L2,….. Ln 8 N5 s% i2 J! d
Step 2:set i=0 : V' h, i: j. Y1 K2 N; N
Step 3:repeat Steps 4 to 8 until i>N
! s! T' @# Y" r0 }" A% Y$ } Step 4: set j=1
L) {+ @$ d* _1 M; P Step 5: repeat Steps 6 and 7 until j>N $ X' R* G" X7 K& Q' m) R2 I
Step 6: print(LI,Lj) / U9 l" k0 W; z4 K" b9 K" p
Step 7: add 1 to the value of j
% G2 `; W$ {2 e Step 8: add 1 to the value of i / G$ k! x, O2 p3 d% O+ b' c
; P( {2 U; [: h5 ]; X. P& O. D
求以上二題的時間複雜度 |
|