[25146] 2016-06-20_每个程序员都应该收藏的算法复杂度速查表

文档创建者:s7ckTeam
浏览次数:1
最后更新:2025-01-18
2016-06-20_每个程序员都应该收藏的算法复杂度速查表 w x y   L i n u x   2 0 1 6 - 0 6 - 2 0 B i g - O   O   便   Y a h o o e B a y L i n k e d I n     G o o g l e   O   - - -   E r i c [ 1 ]       访 访   A r r a y [ 2 ] O ( 1 ) O ( n ) O ( n ) O ( n ) O ( 1 ) O ( n ) O ( n ) O ( n ) O ( n ) S t a c k [ 3 ] O ( n ) O ( n ) O ( 1 ) O ( 1 ) O ( n ) O ( n ) O ( 1 ) O ( 1 ) O ( n ) S i n g l y - L i n k e d   L i s t [ 4 ] O ( n ) O ( n ) O ( 1 ) O ( 1 ) O ( n ) O ( n ) O ( 1 ) O ( 1 ) O ( n ) D o u b l y - L i n k e d   L i s t [ 5 ] O ( n ) O ( n ) O ( 1 ) O ( 1 ) O ( n ) O ( n ) O ( 1 ) O ( 1 ) O ( n ) S k i p   L i s t [ 6 ] O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( n ) O ( n ) O ( n ) O ( n ) O ( n   l o g ( n ) ) H a s h   T a b l e [ 7 ] - O ( 1 ) O ( 1 ) O ( 1 ) - O ( n ) O ( n ) O ( n ) O ( n ) B i n a r y   S e a r c h   T r e e [ 8 ] O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( n ) O ( n ) O ( n ) O ( n ) O ( n ) C a r t e s i a n   T r e e [ 9 ] - O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) - O ( n ) O ( n ) O ( n ) O ( n ) B - T r e e [ 1 0 ] O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( n )
R e d - B l a c k   T r e e [ 1 1 ] O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( n ) S p l a y   T r e e [ 1 2 ] - O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) - O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( n ) A V L   T r e e [ 1 3 ] O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( n )     访 访     Q u i c k s o r t [ 1 4 ] O ( n   l o g ( n ) ) O ( n   l o g ( n ) ) O ( n ^ 2 ) O ( l o g ( n ) ) M e r g e s o r t [ 1 5 ] O ( n   l o g ( n ) ) O ( n   l o g ( n ) ) O ( n   l o g ( n ) ) O ( n ) T i m s o r t [ 1 6 ] O ( n ) O ( n   l o g ( n ) ) O ( n   l o g ( n ) ) O ( n ) H e a p s o r t [ 1 7 ] O ( n   l o g ( n ) ) O ( n   l o g ( n ) ) O ( n   l o g ( n ) ) O ( 1 ) B u b b l e   S o r t [ 1 8 ] O ( n ) O ( n ^ 2 ) O ( n ^ 2 ) O ( 1 ) I n s e r t i o n   S o r t [ 1 9 ] O ( n ) O ( n ^ 2 ) O ( n ^ 2 ) O ( 1 ) S e l e c t i o n   S o r t [ 2 0 ] O ( n ^ 2 ) O ( n ^ 2 ) O ( n ^ 2 ) O ( 1 ) S h e l l   S o r t [ 2 1 ] O ( n ) O ( ( n l o g ( n ) ) ^ 2 ) O ( ( n l o g ( n ) ) ^ 2 ) O ( 1 ) B u c k e t   S o r t [ 2 2 ] O ( n + k ) O ( n + k ) O ( n ^ 2 ) O ( n ) R a d i x   S o r t [ 2 3 ] O ( n k ) O ( n k ) O ( n k ) O ( n + k )   /   A d j a c e n c y   l i s t [ 2 4 ] O ( | V | + | E | ) O ( 1 ) O ( 1 ) O ( | V |   +   | E | ) O ( | E | ) O ( | V | ) I n c i d e n c e   l i s t [ 2 5 ] O ( | V | + | E | ) O ( 1 ) O ( 1 ) O ( | E | ) O ( | E | ) O ( | E | ) A d j a c e n c y   m a t r i x [ 2 6 ] O ( | V | ^ 2 ) O ( | V | ^ 2 ) O ( 1 ) O ( | V | ^ 2 ) O ( 1 ) O ( 1 ) I n c i d e n c e   m a t r i x [ 2 7 ] O ( | V |     | E | ) O ( | V |     | E | ) O ( | V |     | E | ) O ( | V |     | E | ) O ( | V |     | E | ) O ( | E | )   H e a p i f y L i n k e d   L i s t   ( s o r t e d ) [ 2 8 ] - O ( 1 ) O ( 1 ) O ( n ) O ( n ) O ( 1 ) O ( m + n ) L i n k e d   L i s t   ( u n s o r t e d ) [ 2 9 ] - O ( n ) O ( n ) O ( 1 ) O ( 1 ) O ( 1 ) O ( 1 ) B i n a r y   H e a p [ 3 0 ] O ( n ) O ( 1 ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( m + n ) B i n o m i a l   H e a p [ 3 1 ] - O ( 1 ) O ( l o g ( n ) ) O ( l o g ( n ) ) O ( 1 ) O ( l o g ( n ) ) O ( l o g ( n ) ) F i b o n a c c i   H e a p [ 3 2 ] - O ( 1 ) O ( l o g ( n ) ) O ( 1 ) O ( 1 ) O ( l o g ( n ) ) O ( 1 )   O  
B i g   O   C r a c k i n g   t h e   C o d i n g   I n t e r v i e w :   1 5 0   P r o g r a m m i n g   Q u e s t i o n s   a n d   S o l u t i o n s [ 3 3 ] I n t r o d u c t i o n   t o   A l g o r i t h m s ,   3 r d   E d i t i o n [ 3 4 ] D a t a   S t r u c t u r e s   a n d   A l g o r i t h m s   i n   J a v a   ( 2 n d   E d i t i o n ) [ 3 5 ] H i g h   P e r f o r m a n c e   J a v a S c r i p t   ( B u i l d   F a s t e r   W e b   A p p l i c a t i o n   I n t e r f a c e s ) [ 3 6 ] 1 .   E r i c   R o w e l l [ 3 7 ] ,   c r e a t o r   o f   C o n c r e t e . j s [ 3 8 ] ,   a n   H T M L 5   C a n v a s   F r a m e w o r k 2 .   Q u e n t i n   P l e p l e [ 3 9 ] 3 .   M i c h a e l   A b e d [ 4 0 ] 4 .   N i c k   D i z a z z o [ 4 1 ] 5 .   A d a m   F o r s y t h [ 4 2 ] 6 .   D a v i d   D o r f m a n [ 4 3 ] 7 .   J a y   E n g i n e e r [ 4 4 ] 8 .   J e n n i f e r   H a m o n [ 4 5 ] 9 .   J o s h   D a v i s [ 4 6 ] 1 0 .   N o d i r   T u r a k u l o v [ 4 7 ] 1 1 .   B a r t   M a s s e y [ 4 8 ] 1 2 .   V i n n i e   M a g r o [ 4 9 ] 1 3 .   M i g u e l   A m i g o t [ 5 0 ] 1 4 .   D r e w   B a i l e y [ 5 1 ] 1 5 .   A n e e l   N a z a r e t h [ 5 2 ] 1 6 .   R a h u l   C h o w d h u r y [ 5 3 ] 1 7 .   R o b e r t   B u r k e [ 5 4 ] 1 8 .   s t e v e n 4 1 2 9 2 [ 5 5 ] 1 9 .   B r a n d o n   A m o s [ 5 6 ] 2 0 .   M i k e   D a v i s [ 5 7 ] 2 1 .   C a s p e r   V a n   G h e l u w e [ 5 8 ] 2 2 .   J o e l   F r i e d l y [ 5 9 ] 2 3 .   O l e g [ 6 0 ]
2 4 .   R e n f r e d   H a r p e r [ 6 1 ] 2 5 .   P i p e r   C h e s t e r [ 6 2 ] 2 6 .   E r i c   L e f e v r e - A r d a n t [ 6 3 ] 2 7 .   J o n a t h a n   M c E l r o y [ 6 4 ] 2 8 .   S i   P h a m [ 6 5 ] 2 9 .   m c v e r r y [ 6 6 ] 3 0 .   M a x   H o f f m a n n [ 6 7 ] 3 1 .   A l e j a n d r o   R a m i r e z [ 6 8 ] 3 2 .   D a m o n   D a v i s o n [ 6 9 ] 3 3 .   A l v i n   W a n [ 7 0 ] 3 4 .   A l a n   B r i o l a t [ 7 1 ] 3 5 .   D r e w   H a n n a y [ 7 2 ] 3 6 .   A n d r e w   R a s m u s s e n [ 7 3 ] 3 7 .   D e n n i s   T s a n g [ 7 4 ] 3 8 .   B a h a d o r   S a k e t [ 7 5 ] [ 1 ] :   h t t p s : / / t w i t t e r . c o m / e r i c d r o w e l l [ 2 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / A r r a y _ d a t a _ s t r u c t u r e [ 3 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / S t a c k _ ( a b s t r a c t _ d a t a _ t y p e ) [ 4 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / S i n g l y _ l i n k e d _ l i s t # S i n g l y _ l i n k e d _ l i s t s [ 5 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / D o u b l y _ l i n k e d _ l i s t [ 6 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / S k i p _ l i s t [ 7 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / H a s h _ t a b l e [ 8 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / B i n a r y _ s e a r c h _ t r e e [ 9 ] :   h t t p s : / / e n . w i k i p e d i a . o r g / w i k i / C a r t e s i a n _ t r e e [ 1 0 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / B _ t r e e [ 1 1 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / R e d - b l a c k _ t r e e [ 1 2 ] :   h t t p s : / / e n . w i k i p e d i a . o r g / w i k i / S p l a y _ t r e e [ 1 3 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / A V L _ t r e e [ 1 4 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / Q u i c k s o r t [ 1 5 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / M e r g e _ s o r t [ 1 6 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / T i m s o r t [ 1 7 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / H e a p s o r t [ 1 8 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / B u b b l e _ s o r t [ 1 9 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / I n s e r t i o n _ s o r t [ 2 0 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / S e l e c t i o n _ s o r t [ 2 1 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / S h e l l s o r t [ 2 2 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / B u c k e t _ s o r t [ 2 3 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / R a d i x _ s o r t [ 2 4 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / A d j a c e n c y _ l i s t [ 2 5 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / I n c i d e n c e _ l i s t [ 2 6 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / A d j a c e n c y _ m a t r i x [ 2 7 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / I n c i d e n c e _ m a t r i x [ 2 8 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / L i n k e d _ l i s t [ 2 9 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / L i n k e d _ l i s t [ 3 0 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / B i n a r y _ h e a p [ 3 1 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / B i n o m i a l _ h e a p [ 3 2 ] :   h t t p : / / e n . w i k i p e d i a . o r g / w i k i / F i b o n a c c i _ h e a p [ 3 3 ] :   h t t p : / / w w w . a m a z o n . c o m / g p / p r o d u c t / 0 9 8 4 7 8 2 8 0 X / r e f = a s _ l i _ t l ? i e = U T F 8 & c a m p = 1 7 8 9 & c r e a t i v e = 3 9 0 9 5 7 & c r e a t i v e A S I N = 0 9 8 4 7 8 2 8 0 X & l i n k C o d e = a s 2 & t a g = h t c a t u - 2 0 & l i n k I d = B 6 W X I E K J H E B B W J 7 B [ 3 4 ] :   h t t p : / / w w w . a m a z o n . c o m / g p / p r o d u c t / 0 2 6 2 0 3 3 8 4 4 / r e f = a s _ l i _ t l ? i e = U T F 8 & c a m p = 1 7 8 9 & c r e a t i v e = 3 9 0 9 5 7 & c r e a t i v e A S I N = 0 2 6 2 0 3 3 8 4 4 & l i n k C o d e = a s 2 & t a g = h t c a t u - 2 0 & l i n k I d = J 2 P H C T W E A N D 3 Y Q F 4 [ 3 5 ] :   h t t p : / / w w w . a m a z o n . c o m / g p / p r o d u c t / 0 6 7 2 3 2 4 5 3 9 / r e f = a s _ l i _ t l ? i e = U T F 8 & c a m p = 1 7 8 9 & c r e a t i v e = 3 9 0 9 5 7 & c r e a t i v e A S I N = 0 6 7 2 3 2 4 5 3 9 & l i n k C o d e = a s 2 & t a g = h t c a t u - 2 0 & l i n k I d = Y 4 K P A Z H 5 P F H Y X M B A [ 3 6 ] :   h t t p : / / w w w . a m a z o n . c o m / g p / p r o d u c t / 0 5 9 6 8 0 2 7 9 X / r e f = a s _ l i _ t l ? i e = U T F 8 & c a m p = 1 7 8 9 & c r e a t i v e = 3 9 0 9 5 7 & c r e a t i v e A S I N = 0 5 9 6 8 0 2 7 9 X & l i n k C o d e = a s 2 & t a g = h t c a t u - 2 0 & l i n k I d = W U N M G D 5 E A R D J Z K T T [ 3 7 ] :   h t t p s : / / g i t h u b . c o m / e r i c d r o w e l l [ 3 8 ] :   h t t p : / / w w w . c o n c r e t e j s . c o m / [ 3 9 ] :   h t t p s : / / g i t h u b . c o m / q p l e p l e [ 4 0 ] :   h t t p s : / / g i t h u b . c o m / v a u l t [ 4 1 ] :   h t t p s : / / g i t h u b . c o m / n d i z a z z o [ 4 2 ] :   h t t p s : / / g i t h u b . c o m / a g f o r [ 4 3 ] :   h t t p s : / / g i t h u b . c o m / d 3 d a v e [ 4 4 ] :   h t t p s : / / g i t h u b . c o m / j a y 7 5 4 [ 4 5 ] :   h t t p s : / / g i t h u b . c o m / j h a m o n [ 4 6 ] :   h t t p s : / / g i t h u b . c o m / j d a v i s [ 4 7 ] :   h t t p s : / / g i t h u b . c o m / n o d i r t [ 4 8 ] :   h t t p s : / / g i t h u b . c o m / B a r t M a s s e y [ 4 9 ] :   h t t p s : / / g i t h u b . c o m / v m a g r o [ 5 0 ] :   h t t p s : / / g i t h u b . c o m / m i g u e l 5
[ 5 1 ] :   h t t p s : / / g i t h u b . c o m / m a k o s b l a d e [ 5 2 ] :   h t t p s : / / g i t h u b . c o m / W a n d e r i n g S t a r [ 5 3 ] :   h t t p s : / / g i t h u b . c o m / r a h u l c 9 3 [ 5 4 ] :   h t t p s : / / g i t h u b . c o m / s h a r p o b j e c t [ 5 5 ] :   h t t p s : / / g i t h u b . c o m / s t e v e n 4 1 2 9 2 [ 5 6 ] :   h t t p s : / / g i t h u b . c o m / b a m o s [ 5 7 ] :   h t t p s : / / g i t h u b . c o m / d o d g y m i k e [ 5 8 ] :   h t t p s : / / g i t h u b . c o m / c a s p e r v g [ 5 9 ] :   h t t p s : / / g i t h u b . c o m / j f r i e d l y [ 6 0 ] :   h t t p s : / / g i t h u b . c o m / c r i s t a l o l e g [ 6 1 ] :   h t t p s : / / g i t h u b . c o m / r e n f r e d x h [ 6 2 ] :   h t t p s : / / g i t h u b . c o m / p i p e r c h e s t e r [ 6 3 ] :   h t t p s : / / g i t h u b . c o m / e l e f e v r e [ 6 4 ] :   h t t p s : / / g i t h u b . c o m / j o n a t h a n m c e l r o y [ 6 5 ] :   h t t p s : / / g i t h u b . c o m / p h a m t r i s i [ 6 6 ] :   h t t p s : / / g i t h u b . c o m / m c v e r r y [ 6 7 ] :   h t t p s : / / g i t h u b . c o m / m h o f f m a n [ 6 8 ] :   h t t p s : / / g i t h u b . c o m / j 4 n 0 [ 6 9 ] :   h t t p s : / / g i t h u b . c o m / a l l o l e x [ 7 0 ] :   h t t p s : / / g i t h u b . c o m / a l v i n w a n [ 7 1 ] :   h t t p s : / / g i t h u b . c o m / a l a n b r i o l a t [ 7 2 ] :   h t t p s : / / g i t h u b . c o m / d r e w h a n n a y [ 7 3 ] :   h t t p s : / / g i t h u b . c o m / a n d y r a s [ 7 4 ] :   h t t p s : / / g i t h u b . c o m / D e n n i s T T [ 7 5 ] :   h t t p s : / / g i t h u b . c o m / B a h a d o r S a k e t   I D  

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则