Программалау тілдері туралы


Алгоритм күрделілігі тәуелді болатын негізгі факторларды атап өтейік



бет20/40
Дата15.12.2021
өлшемі0,64 Mb.
#101004
түріПрограмма
1   ...   16   17   18   19   20   21   22   23   ...   40
Байланысты:
ишпей куатындар ушин. Таратпандар-1

Алгоритм күрделілігі тәуелді болатын негізгі факторларды атап өтейік :

  • компьютердің жылдамдығы мен ресурстық көлемі ( ең алдымен жедел жады көлемі ) . Шынымен де,процессордың тактілік жиілігі төмен және жедел жады көлемі аз болған сайын арифметикалық және логикалық амалдар баяуырақ орындалып , қарқынсыз әрекет ететін сыртқы жадыны жиі ( көлемді есептер үшін ) қолдануға тура келеді , сондықтан алгоритмді жүзеге асыруға көп уақыт жұмсалады ;

  • таңдалған программалау тілі . Мысалы , Ассемблер тілінде программасы жазылған есеп жалпы жағдайда тезірек шешіледі . Сол алгоритммен , бірақ жоғарырақ деңгейдегі программалау тілі Паскалда жазылған есеппен салыстырғында ;

  • есепті сипаттаудағы таңдалған математикалық әдіс ;

  • программистің шығармашылығы мен тәжірибесі . Жалпы жағдайда сол бір алгоритммен тәжірибелі программист жаңа бастаған қызметтесіне қарағанда тиімді жұмыс жасайтын программа жазып шығады .

Программаның тиімділігі оның өте маңызды сипаттамасы болып табылады . Программа тиімділігі екі жағдайды қамтиды : жады ( немесе кеңістік ) және уақыт . Кеңістіктік тиімділік программаның орындалуына қажет жады мөлшерімен өлшенеді . Компьютерлер жадысының көлемі шектеулі болады . Егер екі программа бір әрекетті жүзеге асырса , онда олардың жадының аз көлемін пайдаланатыны үлкен тиімділік көлемде деп сипатталады . Бірақ соңғы кездері жадының тез арзандауымен , бұл тиімділік өз мәнін жоғалтып келеді . Программаның уақыттық тиімділігі оны орындауға қажет уақыт шамасымен анықталады.


Алгоритм тиімділігін салыстырудың ең жақсы тәсілі олардың күрделілік ретін салыстыру болып табылады . Бұл әдіс уақыттық күрделілікке де , сол сияқты кеңістіктік күрделілікке де қолданылады .

Көп жағдайда уақыттық күрделілік кіріс мәліметтерінен тәуелді болады . Әдетте уақыттық күрделілік п өлшемді кіріс мәліметтерінен тәуелді Т ( n ) ретіне ие деп айтады . Тәжірибеде Т ( п ) шамасын дәл анықтау қиынға соғады . Сондықтан о символын қолданатын асимптотикалық қатысқа жиі жүгінеміз .


Мысалы , алгоритмнің жұмыс жасауына қажет тактілер (әрекеттер) саны 11n квадрат+ 19n : logn+ 3n + 4 өрнегімен сипатталса , онда бұл T ( n ) -нің реті O ( n квадрат ) болатын алгоритм .

Егер сандар микросекундқа сәйкес десек , онда элементінің саны 1048476 жұмыс уақыты Т ( logn ) болатын алгоритмдегі есепке 20 микросекунд , ал жұмыс уақыты T(n квадрат ) болатын алгоритмдегі есепке 12 күннен артық қажет болады .


КүрделІлік функциясы О алгоритмнің қайсыбір айнымалыдан ( немесе айнымалылардан ) тәуелді салыстырмалы жылдамДЫҒЫН өрнектейді . Күрделілік функциясын анықтау үшін үш маңызды ереже орын алған :

1. О ( kf ) = O ( f)

2. О ( fg ) = O ( f ) О ( g ) немесе O( f / g ) = 0 ( f / O ( g )

3. O(f + g ) шамасы O ( f ) және О ( g ) -лардың басымына ( доменанттысына ) тең . Мұнда k тұрақты шаманы , ал f пен с функцияларды білдіреді .


Бірінші ереже тұрақты көбейткіштер алгоритм күрделілігінің ретін анықтауда маңызды емес екенін көрсетеді , мысалы .

О ( 1,5N ) = O ( N ) .

Екінші ережеден шығатыны , екі функция көбейтіндісінің күрделілігі олардың күрделіліктерінің көбейтіндісіне тең , Мысалы :

О ( 17N * N ) = 0 ( 17N ) *O ( N ) = O ( N ) *O ( N ) = O ( N *N ) = O ( N квадрат ) .

Үшінші ережеден Шығатыны , функциялар қосындысының күрделілігі бірінші және екінші қосылғыштардың ішіндегі басымымен анықталады , яғни жоғарғы реттілігі таңдалады , мысалы :

O ( N 5 дәрежесі + N квадрат) =О ( N НІҢ 5 ДӘРЕЖЕСІ )




Достарыңызбен бөлісу:
1   ...   16   17   18   19   20   21   22   23   ...   40




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет