| ½©Á¤·Ä °³³ä | ½©Á¤·Ä ¾Ë°í¸®Áò | ½©Á¤·Ä ºÐ¼® |

½© Á¤·Ä ºÐ¼®

 

¡á ¼º´É

¢¹ ¹ß»ýÇÏ´Â ºñ±³ Ƚ¼ö´Â Á¤·Ä °£°Ý(¸Å°³º¯¼öÀÇ °ª)ÀÌ ¼öÇà¼Óµµ Á¿ì

¢¹ ¸Å°³ º¯¼ö´Â ±Ù»çÀûÀ¸·Î ¼Ò¼öÀ̾î¾ß ÇÑ´Ù°í ¾Ë·ÁÁ® ÀÖÀ¸¸ç,
     ÀÌ·¯ÇÑ °æ¿ìÀÇ ¾Ë°í¸®Áò ¼öÇà½Ã°£Àº O(N(logN)2)

¢¹ Shell(N/2) ÃÖ¾ÇÀÇ °æ¿ì O(N2)

¢¹ Hibberd °£°Ý 1, 3, 7, 15, ..., (2k-1) ÃÖ¾ÇÀÇ °æ¿ì O(N3/2)

¢¹ Sedgewick °£°Ý 9·4i-9·2i+1 ¶Ç´Â 4i-3*2i+1
      { 1, 5, 9, 19, 41, 109, ... } worst O(N4/3), average O(N7/6)

¢¹ ½© Á¤·ÄÀ» ±¸ÇöÇÒ ¶§¿¡´Â Á¤·Ä°£°ÝÀ» ¹è¿­¿¡ ÀúÀåÇÏ¿© »ç¿ëÇÔ

¢¹ ÀÎÁ¢¿ä¼ÒÀÇ ±³È¯¹æ¹ý °³¼±Ã¥ÀÓ, ÃÖ¾Ç N2, ½ÇÁ¦·Î N1.5,  N1.3

¢¹ ½© Á¤·ÄÀº Äü Á¤·Ä ´ÙÀ½À¸·Î ¼öÇà¼Óµµ°¡ ºü¸£°í ¾ÈÁ¤Àû