1 Z Bo |o n o [ o b l i c z n e n i o w a
Z a d . 1
K o r z y s t a j c z t w i e r d z e n i a o r e k u r e n c j i u n i w e r s a l n e j p o d a j o s z a c o w a n i e a s y m p -
t o t y c z n e d l a :
" T ( n ) = 4 T ( n / 4 ) + n
" T ( n ) = 2 T ( n / 3 ) + n
" T ( n ) = 6 T ( n / 4 ) + n 2
" T ( n ) = 2 T ( 2 n ) + n
" T ( n ) = 3 T ( n / 3 ) + n l o g ( n )
Z a d . 2
N a p i s z p s e u d o k o d o p e r a c j i k o l e j k i p r i o r t e t o w e j ( I N S E R T , M A X I M U M , E X T A C T -
M A X ) d l a z w y k Be j k o l e j k i ( z a i m p l e m e n t o w a n e j d l a t a b l i c y ) . M o |n a k o r z y s t a z
p r o c e d u r E N Q U E U E i D E Q U E U E . O s z a c u j z Bo |o n o [ o b l i c z e n i o w o p e r a c j i .
Z a d . 3
N a p i s z p s e u d o k o d p r o c e d u r y I N S E R T ( Q , i , k e y ) , k t r a b d z i e w s t a w i a Ba n a
i - t e j p o z y c j i k o l e j k i w a r t o [ k e y . O p e r a c j a m a s i o d b y w a b e z n a d p i s y w a n i a
|a d n e g o z e l e m e n t w ( o r a z b e z z m i e n i a n i a k o l e j n o [c i ) . O s z a c u j z Bo z o n o [ o b l i -
c z e n i o w t a k i e j o p e r a c j i .
Z a d . 4
N a p i s z p s e u d o k o d f u n k c j i E X T R A C T ( Q , i ) , k t r a b d z i e u s u w a Ba e l e m e n t z
i - t e j p o z y c j i k o l e j k i o r a z z w r a c a Ba j e g o w a r t o [. O s z a c u j z Bo z o n o [ o b l i c z e n i o w
o p e r a c j i .
2 S o r t o w a n i e
Z a d . 5
A l g o r y t m y s o r t o w a n i a Q U I C K S O R T i M E R G E S O R T t o a l g o r y t m y t y p u d z i e l
i z w y c i |a j . K t r y z n i c h m a m n i e j s z y k o s z t s c a l a n i a , d l a c z e g o ?
Z a d . 8
W y k o n a j a l g o r y t m P O D Z I A L n a p o n i |s z e j t a b e l i .
3 4 9 2 5 1 4 6
p r o c e d u r e P O D Z I A L ( A , p , r )
x ! A [ r ]
i ! p - 1
f o r j ! p t o r - 1
d o i f A [ j ] x
t h e n i ! i + 1
A [ i ] ! A [ j ]
A [ i + 1 ] ! A [ r ]
r e t u r n i + 1
1
Z a d . 9
Z m o d y f i k u j a l g o r y t m B U B B L E - S O R T t a k a b y s o r t o w a B n i e r o s n c o .
f o r i ! 1 t o n
d o f o r j ! n d o w n t o i + 1
d o i f A [ j ] < A [ j - 1 ]
t h e n A [ j ] ! A [ j - 1 ]
3 K o p c e
Z a d . 1 1
C z y l i s t a p o s o r t o w a n a m a l e j c o j e s t k o p c e m t y p u M A X . D l a c z e g o ?
Z a d . 1 2
C z y l i s t a p o s o r t o w a n a r o s n c o j e s t k o p c e m t y p u M A X . D l a c z e g o ?
Z a d . 1 3
C z y c i g e l e m e n t w j e s t k o p c e m t y p u M A X .
a ) 2 1 , 1 5 , 1 9 , 9 , 1 0 , 1 1 , 1 2 , 5 , 4 , 1 , 6 , 2 , 4
b ) 2 1 , 1 5 , 1 9 , 1 2 , 1 5 , 1 1 , 1 2 , 5 , 4 , 1 , 6 , 2 , 4
c ) 2 1 , 1 5 , 1 9 , 8 , 1 5 , 1 1 , 1 2 , 9 , 4 , 1 , 6 , 2 , 4
Z a d . 1 4
C o s t a n i e s i z p i e r w s z y m e l . t a b e l i j e [l i w y w o Ba m y H E A P I F Y ( A , 1 ) ?
a ) 7 , 2 5 , 1 9 , 1 9 , 2 0 , 1 1 , 1 2 , 6 , 1 4 , 1 1 , 1 6 , 2 , 4
M A X - H E A P I F Y ( A , i ) l ! L E F T ( i )
r ! R I G H T ( i )
i f ( l h e a p - s i z e [ A ] ) a n d ( A [ l ] > A [ i ] )
t h e n L ! l
e l s e L ! i
i f ( r h e a p - s i z e [ A ] ) a n d ( A [ r ] > A [ L ] )
t h e n L ! r
i f L = i
t h e n A [ i ] ! A [ L ]
M A X - H E A P I F Y ( A , L )
2
Wyszukiwarka
Podobne podstrony:
Złożoność obliczeniowa Zadania 2Złożoność obliczeniowa trudne zadaniazłożoność obliczeniowa algorytmu Maszyny TuringaMIARY ZLOZONOSCI OBLICZENIOWEJobliczenia zadania 5obliczenia zadania 2Algorytmy i struktury danych 02 Rekurencja i złożoność obliczeniowaniweleta obliczenia rzednych luku pionowego teoria zadania1reakcje zlozone zadaniaZadania obliczenioweobliczenia cwiczenia 1 zadania z odpowiedziami niestacjonarneZadanie 2 Wykresy sił przekrojowych w belce złożonejZadania ze zlozonosci algorytmicznychwięcej podobnych podstron