1. ¾Ë°í¸®ÁòÀÇ º¹Àâµµ Ç¥±â¹ýÀ¸·Î ºò-¿À¸Þ°¡ Ç¥±â¹ý, ¼¼Å¸(Theta) Ç¥±â¹ý, ºò-¿À Ç¥±â¹ýÀ» ¼³¸íÇϽÿÀ.
¾Ë°í¸®ÁòÀÇ º¹Àâµµ Ç¥±â¹ýÀº ¾Ë°í¸®ÁòÀÇ ¼º´ÉÀ» ºÐ¼®ÇÒ ¶§ ÁؼöÇÏ´Â Áß¿äÇÑ ¹æ¹ýÀÌ´Ù. ÀÌ·¯ÇÑ Ç¥±â¹ýÀº ÁÖ¾îÁø ÀÔ·ÂÀÇ Å©±â¿¡ µû¶ó ¾Ë°í¸®ÁòÀÌ ¼ÒºñÇÏ´Â ÀÚ¿øÀ» º¸´Ù ¸íÈ®ÇÏ°Ô ÀÌÇØÇÏ°í ¿¹ÃøÇÒ ¼ö ÀÖµµ·Ï µ½´Â´Ù. ¿©·¯ Á¾·ùÀÇ º¹Àâµµ Ç¥±â¹ýÀÌ ÀÖÁö¸¸, ±× Áß¿¡¼µµ ºò-¿À¸Þ°¡ Ç¥±â¹ý, ¼¼Å¸(Theta) Ç¥±â¹ý, ºò-¿À Ç¥±â¹ýÀº Áß¿äÇÏ´Ù. ºò-¿À¸Þ°¡ Ç¥±â¹ýÀº ¾Ë°í¸®ÁòÀÇ ÃÖ¼±ÀÇ ¼º´ÉÀ» ³ªÅ¸³½´Ù. ÀÌ´Â ¾Ë°í¸®ÁòÀÌ Æ¯Á¤ ÀԷ¿¡ ´ëÇØ ÃÖ¼ÒÇÑÀ¸·Î ¼Ò¿äµÇ´Â ½Ã°£ ¶Ç´Â °ø°£ º¹Àâµµ¸¦ Ç¥ÇöÇÑ´Ù. ºò-¿À¸Þ°¡ Ç¥±â¹ýÀº `¥Ø(g(n))` Çü½ÄÀ¸·Î ³ªÅ¸³»¸ç, ÀÌ´Â ¾Ë°í¸®ÁòÀÌ ÃÖ¾ÇÀÇ °æ¿ì¿¡ ºñÇØ ÃÖ¼ÒÇÑ g(n)ÀÇ ¼º´ÉÀ» º¸ÀåÇÑ´Ù´Â ÀǹÌÀÌ´Ù. ¿¹¸¦ µé¾î, ¾î¶² Á¤·Ä ¾Ë°í¸®ÁòÀÌ n°³ÀÇ Ç׸ñ¿¡¼ ÃÖ¼±ÀÇ °æ¿ì O(n log n)ÀÌ´Ù. ÀÌ °æ¿ì, ¾Ë°í¸®ÁòÀº ƯÁ¤ ÀԷ¿¡ ´ëÇؼ± ÃÖ¼ÒÇÑ n log nÀÇ ¼º´ÉÀ» º¸ÀåÇÔÀ» ÀǹÌÇÑ´Ù. ¼¼Å¸(Theta) Ç¥±â¹ýÀº ¾Ë°í¸®ÁòÀÇ ¼º´ÉÀ» Á¤È®ÇÏ°Ô ³ªÅ¸³»´Â µ¥ »ç¿ëµÈ´Ù. ÀÌ´Â ¾Ë°í¸®ÁòÀÌ Æ¯Á¤ ÀÔ·Â Å©±â n¿¡¼ Á¤È®È÷ g(n)ÀÇ ¼º´ÉÀ» º¸ÀÏ ¶§ »ç¿ëµÈ´Ù. ¼¼Å¸ Ç¥±â¹ýÀº `¥è(g(n¡¦(»ý·«)
|