ÿþA i S D : l i s t a 7 , z a d a n i e 4
P a w e B L a s k o [- G r a b o w s k i
n r i n d e k s u 1 6 9 8 2 7
2 9 m a j a 2 0 0 6
1 T r e [
n - e l e m e n t o w y m c i g i e m o j e d n y m z a b u r z e n i u n a z y w a m y d o w o l n y c i g , k t ó r y m o |e b y
o t r z y m a n y z c i g u { 1 , 2 , . . . , n } p o p r z e z w y k o n a n i e j e d n e j t r a n s p o z y c j i . Z a Bó |m y , |e a l -
g o r y t m I n s e r t S o r t b d z i e u r u c h a m i a n y j e d y n i e n a c i g a c h o j e d n y m t a k i m z a b u r z e n i u .
Z b a d a j [r e d n i z Bo |o n o [ a l g o r y t m u p r z y z a Bo |e n i u , |e d l a k a |d e g o n w s z y s t k i e t a k i e c i g i
n - e l e m e n t o w e s j e d n a k o w o p r a w d o p o d o b n e .
2 R o z w i z a n i e
P r z e a n a l i z u j m y p r z e b i e g d z i a Ba n i a a l g o r y t m u n a c i g u
1 , 2 , . . . , i - 1 , j , i + 1 , . . . , j - 1 , i , j + 1 , . . . , n - 1 , n ,
z a u w a |a j c , |e d z i a Ba o n w c z t e r e c h f a z a c h :
1 . S o r t o w a n i e e l e m e n t ó w 1 , 2 , . . . , i - 1 , j . P o n i e w a | k a |d y k o l e j n y r o z p a t r y w a n y e l e m e n t
j e s t w i k s z y o d p o p r z e d n i e g o , w y k o n u j e s i i - 1 p o r ó w n a D ( p i e r w s z e g o e l e m e n t u n i e
p o r ó w n u j e m y z n i c z y m ) .
2 . W s o r t o w a n i e e l e m e n t ó w i + 1 , . . . , j - 1 . K a |d y z n i c h p o r ó w n y w a n y j e s t z e s t o j -
c y m n a p o c z t k u l i s t y j , o d k t ó r e g o j e s t m n i e j s z y , a n a s t p n i e z e s t o j c y m z a n i m ,
o d k t ó r e g o j e s t w i k s z y , z a t e m d l a k a |d e g o z j - i - 1 e l e m e n t ó w w y k o n u j e s i 2
p o r ó w n a n i a .
3 . W s o r t o w a n i e e l e m e n t u i . W s t a w i a n y e l e m e n t j e s t m n i e j s z y o d s t o j c y c h n a p o c z t k u
l i s t y i + 1 , . . . , j - 1 , j ( j - i p o r ó w n a D) , a l e w i k s z y o d s t o j c e g o z a n i m i i - 1
o g ó Be m j - i + 1 p o r ó w n a D.
4 . D o s o r t o w a n i e e l e m e n t ó w j + 1 , . . . , n - 1 , n . T u z n ó w n a p o c z t k u l i s t y z a w s z e s t o i
e l e m e n t m n i e j s z y o d w s o r t o w y w a n e g o , z a t e m w y k o n u j e s i p o 1 p o r ó w n a n i u d l a
k a |d e g o z n - j e l e m e n t ó w .
P o z s u m o w a n i u d o s t a j e m y k o s z t T ( i , j ) = n + 2 ( j - i - 1 ) .
S u b t e l n i e i n n y w y n i k o t r z y m a m y , g d y i = 1 . T u f a z y d z i a Ba n i a a l g o r y t m u s n a s t -
p u j c e :
1 . W s t a w i e n i e j . 0 p o r ó w n a D.
2 . W s o r t o w a n i e e l e m e n t ó w i + 1 , . . . , j - 1 . P i e r w s z y z n i c h p o r ó w n y w a n y j e s t r a z ( t y l k o
z j ) , n a s t p n e p o 2 r a z y ( z j o r a z n a s t p n y m n a l i [c i e , n a k t ó r y m s i z a t r z y m u j ) .
R a z e m 2 ( j - 3 ) + 1 p o r ó w n a D.
1
3 . W s o r t o w a n i e e l e m e n t u i . P o r ó w n u j e m y g o z e w s z y s t k i m i j u | z n a j d u j c y m i s i n a
l i [c i e , g d y | s o d n i e g o w i k s z e j - 1 p o r ó w n a D.
4 . D o s o r t o w a n i e p o z o s t a By c h e l e m e n t ó w . T a k j a k p o p r z e d n i o , w y k o n u j e s i n - j p o -
r ó w n a D.
K o s z t s u m a r y c z n y w y n o s i t e r a z T ( 1 , j ) = n + 2 ( j - 3 ) . O s t a t e c z n i e z a t e m
n + 2 ( j - i - 1 ) d l a i > 1 ,
T ( i , j ) = ( 1 )
n + 2 ( j - i - 1 ) - 2 d l a i = 1 .
A b y p o l i c z y [r e d n i z Bo |o n o [ a l g o r y t m u , n a l e |y t e r a z z s u m o w a w s z y s t k i e T ( i , j ) d l a
1 i < j n ( z r ó w n y m i w a g a m i , b o k a |d y c i g c z y l i k a |d p a r t r a n s p o n o w a n y c h
i n d e k s ó w i , j u z n a j e m y z a r ó w n o p r a w d o p o d o b n ) , i p o d z i e l i p r z e z i l o [ r ó |n y c h c i g ó w ,
n
c z y l i . Z a t e m
2
n - 1 n n n - 1 n
S = T ( i , j ) = ( n + 2 ( j - 1 - 1 ) - 2 ) + ( n + 2 ( j - i - 1 ) ) =
i = 1 j = i + 1 j = 2 i = 2 j = i + 1
n - 1 n
= ( n + 2 ( j - i - 1 ) ) - 2 ( n - 1 ) =
i = 1 j = i + 1
ëø öø
n - 1 n
íø
= ( n - 2 i - 2 ) ( n - i ) + 2 j øø - 2 ( n - 1 ) =
i = 1 j = i + 1
n - 1
( n + i + 1 ) ( n - i )
= ( n - 2 i - 2 ) ( n - i ) + 2 - 2 ( n - 1 ) =
2
i = 1
n - 1
= ( ( n - i ) ( 2 n - i - 1 ) ) - 2 ( n - 1 ) =
i = 1
n - 1
= ( 2 n 2 - n + i ( 1 - 3 n ) + i 2 ) - 2 ( n - 1 ) =
i = 1
n - 1 n - 1
= ( 2 n 2 - n ) ( n - 1 ) + ( 1 - 3 n ) i + i 2 - 2 ( n - 1 ) =
i = 1 i = 1
( n - 1 ) n ( n - 1 ) n ( 2 n - 1 )
= ( 2 n 2 - n ) ( n - 1 ) + ( 1 - 3 n ) + - 2 ( n - 1 ) =
2 6
5 3 4
= n 3 - n 2 - n + 2 . ( 2 )
6 2 3
Zr e d n i a z Bo |o n o [ w y n o s i z a t e m
2 S 5
S ( n ) = n , ( 3 )
n ( n + 1 ) 3
g d z i e p o m i n l i [m y w y r a z y n i |s z y c h r z d ó w .
2
Wyszukiwarka
Podobne podstrony:
AiSD lista 3, zadanie 6AiSD przykladowe zadaniaZadania lista 6 Renty wieczystezadania lista 6 rozrachunki z pracownikamiMatematyka III (Ćw) Lista 03 Równania rzędu drugiego sprowadzalne do równań rzędu pierwszego ZZadania na AiSD uaktualnionewięcej podobnych podstron