1. ¾Ë°í¸®ÁòÀÇ º¹Àâµµ Ç¥±â¹ýÀ¸·Î ºò-¿À¸Þ°¡ Ç¥±â¹ý, ¼¼Å¸(Theta) Ç¥±â¹ý, ºò-¿À Ç¥±â¹ýÀ» ¼³¸íÇϽÿÀ.
¾Ë°í¸®ÁòÀÇ º¹Àâµµ Ç¥±â¹ýÀº ƯÁ¤ ¾Ë°í¸®ÁòÀÇ ¼º´ÉÀ» ºÐ¼®ÇÏ°í ºñ±³ÇÏ´Â µ¥ Áß¿äÇÑ ¿ªÇÒÀ» ÇÑ´Ù. ÀÌ´Â ÁÖ·Î ½Ã°£ º¹Àâµµ¿Í °ø°£ º¹Àâµµ·Î ³ª´µ¾î, ¾Ë°í¸®ÁòÀÌ ¹®Á¦¸¦ ÇØ°áÇÏ´Â µ¥ ¼Ò¸ðÇÏ´Â ½Ã°£°ú ¸Þ¸ð¸®¸¦ ÃøÁ¤ÇÏ´Â ¹æ½ÄÀ¸·Î È°¿ëµÈ´Ù. ÀÌ Áß¿¡¼ ºò¿À(Big-O) Ç¥±â¹ý, ºò-¿À¸Þ°¡(¥Ø) Ç¥±â¹ý, ±×¸®°í ¼¼Å¸(¥È) Ç¥±â¹ýÀº ¾Ë°í¸®ÁòÀÇ È¿À²¼ºÀ» ¼öÇÐÀûÀ¸·Î Ç¥ÇöÇϱâ À§ÇØ »ç¿ëµÈ´Ù. ºò¿À Ç¥±â¹ýÀº ¾Ë°í¸®ÁòÀÇ ÃÖ¾ÇÀÇ °æ¿ì ¼º´ÉÀ» ³ªÅ¸³»¸ç, ÀÔ·Â Å©±â°¡ Ä¿Áú ¶§ ¾Ë°í¸®ÁòÀÌ ¾ó¸¶³ª ¸¹Àº ÀÚ¿øÀ» ¼Ò¸ðÇÏ´ÂÁö¸¦ Ç¥ÇöÇÏ´Â µ¥ »ç¿ëµÈ´Ù. À̴ ƯÁ¤ ÇÔ¼öÀÇ »óÇÑÀ» ³ªÅ¸³»±â ¶§¹®¿¡, ƯÁ¤ ÀԷ¿¡ ´ëÇÑ ½Ã°£ º¹Àâµµ°¡ ¾ðÁ¦µçÁö ±× ÇÔ¼ö¸¦ ÃÊ°úÇÏÁö ¾ÊÀ½À» º¸ÀåÇÑ´Ù. ¿¹¸¦ µé¾î, ¾î¶² ¾Ë°í¸®ÁòÀÌ O(n^ÀÇ ½Ã°£ º¹Àâµµ¸¦ °¡Áø´Ù°í ÇÒ ¶§, ÀÌ´Â ÀÔ·ÂÀÇ Å©±â°¡ nÀÏ ¶§ ¾Ë°í¸®ÁòÀÇ ½ÇÇà ½Ã°£ÀÌ n^2ÀÇ ºñ·Ê½Ä ¾Æ·¡¿¡ ¸Ó¹®´Ù´Â ÀǹÌÀÌ´Ù. ÀÌ´Â ¾Ë°í¸®ÁòÀÇ ¼º´ÉÀ» Æò°¡ÇÏ´Â µ¥ ÀÖ¾î Áß¿äÇÑ Á¤º¸·Î, ÃÖ¾ÇÀÇ »óȲ¿¡¼µµ ½Ã°£À̳ª °ø°£ÀÌ ÀÌ ¼öÁØ ÀÌ»óÀ¸·Î Áõ°¡ÇÏÁö ¾ÊÀ» °ÍÀÓÀ» º¸ÀåÇϱ⠶§¹®¡¦(»ý·«)
|