алгоритмдік күрделілік. Іздеу алгоритмдері

Сіз O (log n) сияқты белгілерді жиі кездестірдіңіз немесе кез келген алгоритмдерге қатысты «логарифмдік есептеу күрделілігі» сияқты тіркестерді естідіңіз. Егер сіз әлі де бұл нені білдіретінін түсінбесеңіз, бұл мақала сізге арналған.

Күрделілік рейтингі

Алгоритмдердің күрделілігі әдетте орындалу уақыты немесе пайдаланылған жады бойынша бағаланады. Екі жағдайда да күрделілік кіріс деректерінің өлшеміне байланысты: 100 элементтен тұратын массив 1000-ға ұқсас массивке қарағанда жылдамырақ өңделеді. Сонымен қатар, аз адамдар нақты уақыт туралы ойламайды: бұл процессорға байланысты, деректер түрі, бағдарламалау тілі және басқа да көптеген параметрлер. Тек асимптотикалық күрделілік маңызды, яғни кіріс өлшемі шексіздікке ұмтылатындықтан күрделілік.

Кейбір алгоритм n кіріс деректер элементтерін өңдеу үшін 4n 3 + 7n шартты операцияларды орындауы керек делік. n ұлғайған сайын, n санын текшеге көтеру оны 4-ке көбейту немесе 7n қосудан гөрі жалпы орындалу уақытына айтарлықтай көбірек әсер етеді. Содан кейін біз бұл алгоритмнің уақыттық күрделілігі O(n 3) тең екенін айтамыз, яғни ол тек кіріс деректерінің өлшеміне байланысты.

О капиталын (немесе O-белгілеу деп аталатын) пайдалану математикадан келеді, мұнда ол функциялардың асимптотикалық әрекетін салыстыру үшін қолданылады. Ресми түрде O(f(n)) алгоритмнің жұмыс уақыты (немесе бос тұрған жад көлемі) f(n) көбейтілген кейбір тұрақтыдан жылдам емес кіріс деректерінің көлеміне байланысты өсетінін білдіреді.

Мысалдар

O(n) – сызықтық күрделілік

Мұндай күрделілікте, мысалы, сұрыпталмаған массивтегі ең үлкен элементті табу алгоритмі бар. Қайсысы ең үлкен екенін анықтау үшін массивтің барлық n элементінен өтуіміз керек.

O(log n) - журналдың күрделілігі

Ең қарапайым мысал - екілік іздеу. Егер массив сұрыпталса, онда екіге бөлу арқылы белгілі бір мән бар-жоғын тексеруге болады. Ортаңғы элементті тексеріп көрейік, егер ол қалағаннан үлкен болса, онда массивтің екінші жартысын алып тастаймыз - ол сөзсіз жоқ. Егер аз болса, онда керісінше - біз бастапқы жартысын тастаймыз. Осылайша біз жартыға бөлуді жалғастырамыз, нәтижесінде log n элементтерін тексереміз.

O(n 2) – квадраттық күрделілік

Мұндай күрделілікте, мысалы, кірістіру сұрыптау алгоритмі бар. Канондық іске асыруда ол екі кірістірілген циклден тұрады: біреуі бүкіл массив арқылы өту үшін, екіншісі сұрыпталған бөліктегі келесі элемент үшін орын табу үшін. Осылайша, әрекеттер саны n * n, яғни n 2 сияқты массив өлшеміне байланысты болады.

Басқа қиындық рейтингтері бар, бірақ олардың барлығы бірдей принципке негізделген.

Сондай-ақ, алгоритмнің жұмыс уақыты кіріс деректерінің өлшеміне мүлдем тәуелді емес. Сонда күрделілік O(1) ретінде белгіленеді. Мысалы, массивтің үшінші элементінің мәнін анықтау үшін элементтерді есте сақтау немесе олардың үстінен бірнеше рет қайталау қажет емес. Сізге әрқашан кіріс деректер ағынындағы үшінші элементті күту қажет және бұл кез келген деректер көлемі үшін есептеу бірдей уақытты қажет ететін нәтиже болады.

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

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

Белгілі бір бағдарламаның нақты тәуелділігін табу өте қиын міндет. Осы себепті ол әдетте шектеулі асимптотикалық бағалауларбұл функция, яғни параметрдің үлкен мәндері үшін оның шамамен әрекетінің сипаттамасы . Кейде асимптотикалық бағалаулар үшін екі функция арасындағы дәстүрлі қатынас («Үлкен О» оқыңыз) пайдаланылады. , оның анықтамасын математикалық талдау бойынша кез келген оқулықтан табуға болады, дегенмен ол жиірек қолданылады эквиваленттік қатынас(«тета үлкен» деп оқыңыз). Оның формальды анықтамасы, мысалы, кітапта, дегенмен әзірге бұл бізге түсіну үшін жеткілікті болады бұл мәселеконтурда.

Бірінші мысал ретінде санның факториалын табу үшін жаңа ғана қарастырған бағдарламаларға оралайық. Факториалды табу үшін орындалатын амалдардың санын көру оңай ! бірінші жуықтаудағы сан осы санға тура пропорционал, өйткені бұл бағдарламадағы циклдің (итерацияның) қайталану саны -ге тең. Мұндай жағдайда бағдарламада (немесе алгоритмде) бар деп айту әдеттегідей сызықтық күрделілік(күрделілігі немесе).

Факториалды тезірек есептеу мүмкін бе? Иә болып шығады. Итерацияны да, рекурсияны да қолданбай-ақ, жоғарыда аталған барлық бағдарламалар орындайтын мәндер үшін дұрыс нәтиже беретін бағдарламаны жазуға болады. Оның күрделілігі болады, бұл шын мәнінде циклдар мен рекурсивті шақыруларды пайдаланбай қандай да бір формула бойынша есептеулерді ұйымдастыруды білдіреді!

Фибоначчи санын есептеу мысалы қызықтырақ. Оны зерттеу барысында, шын мәнінде, оның күрделілігі бұрыннан белгілі болды экспоненциалдыжәне тең. Мұндай бағдарламалар іс жүзінде іс жүзінде қолданылмайды. Онымен 40-шы Фибоначчи санын есептеу арқылы оны тексеру өте оңай. Осы себепті келесі мәселе өте өзекті болып табылады.

5.4-тапсырма сызықтық күрделілік.

Міне, j және k айнымалылары екі дәйекті Фибоначчи санының мәндерін қамтитын осы мәселенің шешімі.

Бағдарлама мәтіні

public класс FibIv1 ( public static void main(String args) шығарады Ерекше жағдай ( int n = Xterm.inputInt("Enter n ->"< 0) { Xterm.print(" не определено\n"); } else if (n < 2) { Xterm.println(" = " + n); } else { long i = 0; long j = 1; long k; int m = n; while (--m >0) ( k = j; j += i; i = k; ) Xterm.println(" = " + j); )))

Келесі сұрақ өте табиғи - Фибоначчи сандарын одан да жылдам табуға бола ма?

Математиканың белгілі бір бөлімдерін зерттегеннен кейін --ші Фибоначчи саны үшін келесі формуланы шығару өте оңай, оны шағын мәндерді тексеру оңай:

Оның негізінде қайталануды немесе рекурсияны қолданбайтын күрделілігі бар бағдарламаны жазу оңай болып көрінуі мүмкін.

Бағдарлама мәтіні

public класс FibIv2 ( public static void main(String args) throws Exception ( int n = Xterm.inputInt("Enter n -> "); double f = (1.0 + Math.sqrt(5.)) / 2.0; int j = (int)(Math.pow(f,n) / Math.sqrt(5.) + 0,5); Xterm.println("f(" + n + ") = " + j); ) )

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

Фибоначчи санын есептеу үшін осындай алгоритм бар, оны бағдарламалық қамтамасыз етуді іске асыру біз қосымша түсініктемелерсіз береміз, әйтпесе сізге тым көп түсіндіру керек (Фибоначчи сандарын екінші ретті белгілі бір матрицаның қуаттарымен қосу, класстарды пайдалана отырып, матрицалармен жұмыс, матрицаны дәрежеге жылдам көтеру алгоритмі) .

5.5-тапсырма. Бар --ші Фибоначчи санын басып шығаратын программа жазыңыз логарифмдік күрделілік.

Бағдарлама мәтіні

жалпы класс FibIv3 ( public static void main(String args) шығарады Ерекшелік ( int n = Xterm.inputInt("Enter n -> "); Xterm.print("f(" + n + ")"); if (n)< 0) { Xterm.println(" не определено"); } else if (n < 2) { Xterm.println(" = " + n); } else { Matrix b = new Matrix(1, 0, 0, 1); Matrix c = new Matrix(1, 1, 1, 0); while (n>0) ( if ((n&1) == 0) ( n >>>= 1; c.square(); ) else ( n -= 1; b.mul(c); ) ) Xterm.println(" = " +b.fib()); ) ) ) класс матрицасы ( жеке long a, b, c, d; public Matrix(long a, long b, long c, long d) ( this.a = a; this.b = b; this.c = c; this.d = d; ) public void mul(Matrix m) ( long a1 = a*m.a+b*mc; ұзын b1 = a*m.b+b*md; ұзын c1 = c*m.a+ d *mc; long d1 = c*m.b+d*md; a = a1; b = b1; c = c1; d = d1; ) public void square() ( mul(this); ) public long fib( ) (қайтару б;))

Егер сіз осы және алдыңғы бағдарламаны пайдаланып Фибоначчидің он миллионыншы санын есептеуге тырыссаңыз, онда есептеу уақытындағы айырмашылық өте айқын болады. Өкінішке орай, long түріндегі сандардың шектеулі ауқымына байланысты нәтиже дұрыс емес болады (екі жағдайда да).

Қорытындылай келе, біз ұсынамыз салыстыру кестесіәр түрлі күрделіліктегі алгоритмдердің орындалу уақытын және компьютердің жылдамдығы артқан сайын жылдам алгоритмдерді пайдаланудың маңыздылығының айтарлықтай арта түсетінін түсіндіріңіз.

Күрделілігі бар бір есепті шешудің төрт алгоритмін , , және сәйкесінше қарастырайық. Осы алгоритмдердің екіншісін параметр мәні бар кейбір компьютерде орындау үшін дәл бір минут уақыт қажет делік. Сонда параметрдің әртүрлі мәндері бар бір компьютерде осы төрт алгоритмнің барлығының орындалу уақыты шамамен 10 300 000 жылдағыдай болады.

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

Компьютерлер жылдамдығының жоғарылауымен сол немесе басқа алгоритмнің жұмысы қолайлы уақытта аяқталатын параметрлердің мәндері де артады. Осылайша, мәннің орташа мәні артады, демек, жылдам және баяу алгоритмдердің орындалу уақыттарының қатынасының мәні артады. Қалай жылдамырақ компьютер, нашар алгоритмді пайдаланған кезде салыстырмалы жоғалту соғұрлым көп болады!

Есепті шешудің бір алгоритмі болса, сол есепті шешу үшін басқа да көптеген алгоритмдерді ойлап табуға болады. Белгілі бір мәселені шешу үшін қай алгоритм тиімді? Алгоритмді мүмкін болатындар жиынтығынан таңдау үшін қандай критерийлерді қолдану керек? Әдетте, біз алгоритм туралы шешімді адам орындаушысының бағалауы негізінде жасаймыз. Алгоритм бізге күрделі болып көрінеді, егер оны мұқият зерттегеннен кейін де оның не істейтінін түсіне алмасақ. Алгоритмді күрделі және түсініксіз деп атауға болады, себебі оның көптеген шартты тексерулер мен ауысуларды қамтитын тармақталған логикалық құрылымы бар. Дегенмен, компьютер үшін мұндай алгоритмді жүзеге асыратын программаның орындалуы қиын болмайды, өйткені ол командаларды бірінен соң бірін орындайды және оның көбейту операциясы немесе шартты тексеру болуы компьютер үшін маңызды емес.

Сонымен қатар, қайталанатын әрекеттер қатарынан жазылатын (циклдік құрылымды қолданбай) күрделі алгоритм жазуға болады. Дегенмен, мұндай алгоритмді компьютерде жүзеге асыру тұрғысынан алғанда, бағдарлама цикл операторын қолдана ма (мысалы, «Сәлеметсіз бе» сөзі 10 рет көрсетіледі) немесе сөзді көрсетуге арналған операторлар ма, іс жүзінде ешқандай айырмашылық жоқ. «Сәлем» 10 рет ретімен жазылады.

Алгоритмдердің тиімділігін бағалау, түсінігі алгоритмнің күрделілігі.

Анықтама. есептеу процесі,алгоритммен генерацияланатын – бұл алгоритмді орындау кезінде өткен алгоритм қадамдарының тізбегі.

Анықтама. Алгоритмнің күрделілігіэлементар қадамдар саны болып табылады есептеу процесібұл алгоритм.

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

Анықтама. Алгоритмнің уақыттық күрделілігіоны аяқтау үшін қажет T уақыты. Ол бір әрекетті орындаудың орташа уақытына қарапайым әрекеттер санының көбейтіндісіне тең: T = kt.

Қаншалықты талгоритмді жүзеге асыратын орындаушыға байланысты, алгоритмнің күрделілігі ең алдымен к.Әлбетте, ең көп дәрежеде алгоритмді орындаудағы операциялардың саны өңделетін деректер көлеміне байланысты. Шынында да, 100 тегі бар тізімді алфавит бойынша сұрыптау үшін 100 000 фамилиядан тұратын тізімді сұрыптаудан гөрі әлдеқайда аз әрекеттер қажет. Сондықтан алгоритмнің күрделілігі енгізілген деректер көлемінің функциясы ретінде көрсетіледі.

А алгоритмі болсын. Ол үшін параметр бар бірақ,алгоритммен өңделетін деректер көлемін сипаттайтын бұл параметр жиі аталады тапсырма өлшемі.арқылы белгілеңіз T(n)алгоритмнің орындалу уақыты f- кейбір функциялардан П.

Анықтама.Соны айтамыз T(n)алгоритмнің өсу реті бар f(n), немесе,басқаша айтқанда, алгоритм бар теориялық күрделілікO * (f(n)), егер мұндай тұрақтылар болса 1-ден, 2-ден> 0 және сан n 0,не c 1 f(n)) < T(p)< c 2 f(n) барлығына n >= n 0 .Мұнда функция деп болжанады f(n)теріс емес, бірақ кем дегенде n >= n 0 .Егер үшін T(p)шарты T(n)<= cf(n),онда алгоритм бар деп айтылады теориялық күрделілік O(p) (n-ден үлкен «o» оқыңыз).

Мәселен, мысалы, деректерді оқу және оларды жедел жадыға қою операцияларын ғана орындайтын алгоритм сызықтықкүрделілік 0(n).Тікелей іріктеу сұрыптау алгоритмі бар квадраттықкүрделілік 0(p 2) ,өйткені кез келген массивді сұрыптау кезінде орындау керек (p 2 - p) / 2салыстыру операциялары (бір уақытта ауыстыру операциялары мүлде болмауы мүмкін, мысалы, реттелген массивте, ең нашар жағдайда орындау қажет болады Пауыстыру). Ал көбейту алгоритмінің күрделілігі матрицалар(кестелер) өлшемі П x Пқазірдің өзінде болады текше O(n 3) , өйткені алынған матрицаның әрбір элементі талап етеді Пкөбейту және n - 1толықтырулар, бірақ барлық осы элементтер n 2.

Есепті шешу үшін кез келген күрделіліктегі алгоритмдерді жасауға болады. Олардың ішінде ең жақсысын пайдалану қисынды, яғни. ең аз күрделілікке ие.

Күрделілігімен қатар алгоритмнің маңызды сипаттамасы болып табылады тиімділігі.Тиімділік келесі талаптың орындалуы ретінде түсініледі: тек бүкіл алгоритм ғана емес, сонымен қатар оның әрбір қадамы орындаушы оларды шектеулі ақылға қонымды уақытта аяқтай алатындай болуы керек. Мысалы, егер келесі күнге ауа райы болжамын жасайтын алгоритм бір апта ішінде орындалатын болса, онда оның күрделілігі ұқсас есептер класы үшін минималды болса да, мұндай алгоритм ешкімге қажет емес.

Егер компьютерде жүзеге асырылатын алгоритмдерді қарастыратын болсақ, онда шектеулі көлемде орындау талабына ақылға қонымды мерзімде орындалу талабы қосылады. жедел жады.

Көптеген бағдарламалау тілдерінде дәрежеге шығару операциясы жоқ екені белгілі, сондықтан мұндай алгоритмді программист өз бетімен жазуы керек. Көрсеткіштерге шығару операциясы көбейту амалдары арқылы жүзеге асады; дәреже өскен сайын, көп уақытты қажет ететін көбейту амалдарының саны артады. Сондықтан тиімді дәрежеге шығару алгоритмін құру мәселесі өзекті болып табылады.

Нақты санның натурал дәрежесін жылдам есептеу әдісін қарастырайық X.Бұл әдіс біздің дәуірімізге дейін Ежелгі Үндістанда сипатталған.

Жазып алайық Пекілік жүйеде.

Осы жазбадағы әрбір «1»-ді жұп әріптермен ауыстырайық KH,және әрбір «О» - К әрпі.

CHs ең сол жақ жұбын жойыңыз.

Солдан оңға қарай оқылатын нәтиже жол жылдам есептеу ережесін береді xn,хат болса TOнәтижені және әріпті квадраттау операциясы ретінде қарастырылады X- нәтижені көбейту операциясы ретінде X.Бастапқыда нәтиже X.

Мысал 1. x-ті n = 100 дәрежесіне көтеріңіз.

n санын екілік санау жүйесіне аударайық: n \u003d 100 10 \u003d 1100100,

Біз KHKKKKKKKKK тізбегін құрастырамыз

Сол жақтағы AX-ты сызып тастаңыз => KHKKKKKK

Біз қалаған мәнді есептейміз

K => біз x квадратын аламыз => х 2 аламыз,

X => нәтижені х-ке көбейтіңіз => х 3-ті алыңыз

K => нәтиженің квадраты => x 6 алыңыз

K => нәтижені квадраттаймыз => x 12 аламыз,

K => нәтиженің квадраты => x 24 алыңыз,

X => нәтижені x-ке көбейтіңіз => x 25 алыңыз

K => нәтиженің квадраты => x 50 алыңыз

K => нәтиженің квадраты => x 100 алыңыз.

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

Мысалы, n = 49 болғанда студенттер келесі тиімді дәрежеге шығару алгоритмін жасай алады:

Бұл алгоритмді жүзеге асыру кезінде 7 көбейту амалы орындалды («маңдайда» есептеу кезінде 48 операцияның орнына) және 3 ұяшық (айнымалыны сақтау үшін) X, мәнді сақтау үшін x 16және әрбір қадамда алынған ағымдағы нәтижені сақтау үшін). Егер біз «Жылдам дәрежеге шығару» алгоритмін қолдансақ, онда біз бірдей операциялар санын аламыз (7 көбейту амалы), бірақ бұл алгоритмді жүзеге асыру үшін (айнымалыны сақтау үшін) тек 2 ұяшық қажет. Xжәне ағымдағы нәтижені сақтау үшін).

Көбейту операциясының өзі процессорда «маңдайда» емес, қайтадан тиімді рекурсивті алгоритмдер арқылы жүзеге асырылады. Осы алгоритмдердің бірі туралы Reader бағдарламасында оқи аласыз. Ежелгі Египетте белгілі болған «жылдам» көбейту алгоритмін қарастырамыз, ол «орыс» немесе «шаруа» әдісі деп те аталады. Осы алгоритмді қолданудың мысалын қарастырайық.

Мысал 2. «Орысша» әдісі арқылы 23-ті 43-ке көбейтейік.

Жауабы: 23 x 43 = 23 + 46 + 184 + 736 = 989.

Қорытынды қосындыға бірінші бағандағы сандар кіреді, олардың жанында екінші бағанда тақ сандар бар.

O(1) -Бағдарламадағы операциялардың көпшілігі тек бір рет немесе бірнеше рет орындалады. Тұрақты күрделілік алгоритмдері. Деректер өлшеміне қарамастан әрқашан бірдей уақытты қажет ететін кез келген алгоритм бар тұрақты күрделілік.

O(N) -Бағдарламаның орындалу уақыты сызықтықәдетте кіріс деректерінің әрбір элементін тек сызықтық бірнеше рет өңдеу қажет болғанда.

O(N 2), O(N 3), O(N a) - Көпмүшелік күрделілік.

O(N 2)-квадрат күрделілік, O(N 3)-кубтық күрделілік

O(Log(N)) -Бағдарламаның орындалу уақыты логарифмдік, N ұлғайған сайын бағдарлама әлдеқайда баяу жұмыс істей бастайды.Мұндай жұмыс уақыты әдетте бөлетін бағдарламаларда кездеседі. үлкен мәселекішкентайларға бөліп, оларды бөлек шешеді.

O(N*log(N)) -Мұндай жұмыс уақытында алгоритмдер бар үлкен мәселені кішіге бөлу, содан кейін оларды шешіп, шешімдерін қосыңыз.

O(2 N) = Көрсеткіштік күрделілік.Мұндай алгоритмдер көбінесе дөрекі күш деп аталатын тәсілден туындайды.

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

Циклдарсыз және рекурсивті шақыруларсыз алгоритмдер тұрақты күрделілікке ие. Егер рекурсия және циклдар болмаса, барлық басқару құрылымдарын тұрақты күрделіліктегі құрылымдарға келтіруге болады. Демек, бүкіл алгоритм тұрақты күрделілікпен сипатталады.

Алгоритмнің күрделілігін анықтау негізінен циклдар мен рекурсивті шақыруларды талдауға түседі.

Мысалы, массив элементтерін өңдеу алгоритмін қарастырайық.
i:=1 үшін N орындаңыз
Баста
...
Соңы;

Бұл алгоритмнің күрделілігі O(N), өйткені цикл денесі N рет орындалады, ал цикл денесінің күрделілігі O(1).

Егер бір цикл екіншісінің ішіне кірістірілген болса және екі цикл де бірдей айнымалының өлшеміне тәуелді болса, онда бүкіл құрылыс квадраттық күрделілікпен сипатталады.
i:=1 үшін N орындаңыз
j:=1 үшін N орындаңыз
Баста
...
Соңы;
Бұл бағдарламаның күрделілігі O(N 2) болып табылады.

Бар Алгоритмнің күрделілігін талдаудың екі жолы: төменнен жоғарыға (ішкі басқару құрылымдарынан сыртқы басқару құрылымдарына дейін) және төмендеу (сыртқы және ішкі жағынан).

O(H)=O(1)+O(1)+O(1)=O(1);
O(I)=O(N)*(O(F)+O(J))=O(N)*O(шарт басым)=O(N);
O(G)=O(N)*(O(C)+O(I)+O(K))=O(N)*(O(1)+O(N)+O(1))=O (N 2);
O(E)=O(N)*(O(B)+O(G)+O(L))=O(N)* O(N 2)= O(N 3);
O(D)=O(A)+O(E)=O(1)+ O(N 3)= O(N 3)

Күрделілігі бұл алгоритм O(N3).

Әдетте, бағдарламаның орындалу уақытының шамамен 90% қайталауды қажет етеді және тек 10% нақты есептеу болып табылады. Бағдарламалардың күрделілігін талдау қай фрагменттердің осы 90% -ға түсетінін көрсетеді - бұл ең үлкен ұя салу тереңдігінің циклдері. Қайталаулар кірістірілген циклдар немесе кірістірілген рекурсия ретінде ұйымдастырылуы мүмкін.

Бұл ақпаратты бағдарламашы тиімдірек бағдарлама құру үшін келесі жолмен пайдалана алады. Ең алдымен, қайталанулардың ұя салу тереңдігін азайтуға тырысуға болады. Содан кейін ең кірістірілген циклдардағы мәлімдемелер санын азайтуды қарастырыңыз. Орындау уақытының 90% ішкі циклдердің орындалуы болса, онда бұл шағын бөлімдердің 30% қысқаруы бүкіл бағдарламаның орындалу уақытының 90% * 30% = 27% қысқаруына әкеледі.

Бұл ең қарапайым мысал.

Математиканың жеке бөлімі алгоритмдердің тиімділігін талдаумен айналысады, ал ең оңтайлы функцияны табу оңай емес.

Баға берейік массивтегі екілік іздеу алгоритмі – дихотомия.

Алгоритмнің мәні: массивтің ортасына өтіп, кілттің ортаңғы элемент мәніне сәйкестігін іздейміз. Сәйкестікті таба алмасақ, ортаңғы элементтің салыстырмалы кілт өлшемі мен мәнін қарастырамыз, содан кейін тізімнің төменгі немесе жоғарғы жартысына жылжимыз. Осы жартысында біз қайтадан ортаны іздейміз және оны қайтадан кілтпен салыстырамыз. Егер ол жұмыс істемесе, біз ағымдағы интервалды қайтадан екіге бөлеміз.

функцияны іздеу(төмен, жоғары, кілт: integer): бүтін;
var
орта, деректер: бүтін;
баста
төмен болған кезде<=high do
баста
mid:=(төмен+жоғары) div 2;
деректер:=a;
егер кілт = деректер болса
іздеу:=орта
басқа
кілт болса< data then
жоғары:=орта-1
басқа
төмен:=орта+1;
Соңы;
іздеу:=-1;
Соңы;

Циклдің бірінші итерациясы бүкіл тізіммен айналысады. Әрбір келесі итерация ішкі тізім өлшемін екі есе азайтады. Сонымен, алгоритм үшін тізімнің өлшемдері

n n/2 1 n/2 2 n/2 3 n/2 4 ... n/2 м

Ақырында бүтін m болатындай болады

н/2м<2 или n<2 m+1

Өйткені m – n/2 м болатын бірінші бүтін сан<2, то должно быть верно

n/2 м-1 >=2 немесе 2 м =

Осыдан шығады
2 м = Теңсіздіктің әрбір бөлігінің логарифмін аламыз және аламыз
m= m мәні = болатын ең үлкен бүтін сан<х.
Сонымен, O(log 2 n).

Әдетте, шешілетін мәселенің табиғи «өлшемі» (әдетте ол өңдейтін деректер көлемі) болады, оны біз N деп атаймыз. Сайып келгенде, біз N өлшемді деректерді өңдеу үшін бағдарламаға кететін уақыттың өрнекін алғымыз келеді. N функциясы. Әдетте, бізді орташа жағдай қызықтырмайды – «типтік» кірістердегі бағдарламаның күтілетін жұмыс уақыты, ал ең нашар жағдай — ең нашар ықтимал кірістердегі бағдарламаның күтілетін жұмыс уақыты.

Кейбір алгоритмдер нақты математикалық формулалар орташа және ең нашар жағдайлар үшін белгілі деген мағынада жақсы түсініледі. Мұндай формулалар математикалық сипаттамалар бойынша орындалу уақытын табу үшін бағдарламаларды мұқият зерттеп, содан кейін олардың математикалық талдауын орындау арқылы жасалады.

Мұндай талдаудың бірнеше маңызды себептері:
1. Жоғары деңгейлі тілде жазылған бағдарламалар машиналық кодтарға аударылады және белгілі бір операторды орындауға қанша уақыт кететінін түсіну қиын болуы мүмкін.
2. Көптеген бағдарламалар енгізілген деректерге өте сезімтал және олардың тиімділігі оларға өте тәуелді болуы мүмкін. Орташа жағдай бағдарлама қолданылатын деректерге қатысы жоқ математикалық фантастика болуы мүмкін, ал ең нашар жағдай екіталай.

Ең жақсы, орташа және ең нашар жағдайлар сұрыптауда өте үлкен рөл атқарады.
Сұрыптау кезіндегі есептеулердің көлемі

O-күрделілігін талдау көптеген практикалық қолданбаларда кең таралған. Дегенмен, оның шектеулерін нақты түсіну керек.

TO тәсілдің негізгі кемшіліктерімыналарды қамтуы мүмкін:
1) күрделі алгоритмдер үшін O-бағаларын алу, әдетте, өте қиын немесе мүмкін емес дерлік;
2) күрделілікті «орташа» анықтау жиі қиын,
3) O-бағалаулары алгоритмдер арасындағы нақты айырмашылықтарды көрсету үшін тым өрескел,
4) О-талдау деректердің шағын көлемін өңдеу кезінде алгоритмдердің әрекетін талдау үшін тым аз ақпарат береді (немесе мүлде жоқ).

O-нотациясында күрделілікті анықтау тривиальды тапсырмадан алыс. Атап айтқанда, екілік іздеудің тиімділігі ілмектердің кірістіру тереңдігімен емес, әрбір дәйекті әрекетті таңдау әдісімен анықталады.

Тағы бір қиындық – «орташа жағдай» анықтамасы. Әдетте алгоритмнің жұмыс жағдайларын болжау мүмкін еместігіне байланысты мұны істеу өте қиын. Кейде алгоритм үлкен, күрделі бағдарламаның фрагменті ретінде пайдаланылады. Кейде аппараттық және/немесе операциялық жүйенің өнімділігі немесе компилятордың кейбір құрамдас бөлігі алгоритмнің күрделілігіне айтарлықтай әсер етеді. Көбінесе бір алгоритмді көптеген әртүрлі қолданбаларда қолдануға болады.

Алгоритмнің уақыт күрделілігін «орташа» талдаумен байланысты қиындықтарға байланысты жиі ең нашар және жақсы жағдайларды бағалаумен қанағаттануға тура келеді. Бұл ұпайлар негізінен «орташа» күрделілік бойынша төменгі және жоғарғы шекараларды анықтайды. Шындығында, егер алгоритмнің күрделілігін «орташа» талдау мүмкін болмаса, Мерфи заңдарының бірін ұстану керек, оған сәйкес ең нашар жағдай үшін алынған бағалау күрделіліктің «орташа есеппен» жақсы жуықтауы бола алады. «.

Мүмкін, O-функцияларының негізгі кемшілігі олардың шамадан тыс кедір-бұдыры болуы мүмкін. Егер А алгоритмі қандай да бір тапсырманы 0,001*N с ішінде орындаса, ал B алгоритмі оны шешу үшін 1000*N с уақытты қажет ететін болса, онда В A-дан миллион есе жылдамырақ. Соған қарамастан, A және B бірдей уақыт күрделілігін O(N) бөліседі.

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

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

Алгоритмнің интеллектуалды күрделілігін талдау кезінде алгоритмдердің түсініктілігі және оларды әзірлеудің күрделілігі зерттеледі.

Күрделіліктің барлық үш формасы әдетте өзара байланысты. Әдетте, уақыттың күрделілігін жақсы бағалауы бар алгоритмді жасау кезінде оның кеңістіктік және/немесе интеллектуалды күрделілігін құрбан ету керек. Мысалы, жылдам сұрыптау алгоритмі таңдау сұрыптау алгоритміне қарағанда айтарлықтай жылдамырақ. Сұрыптау жылдамдығын арттырудың пайдасы сұрыптау үшін қажет көбірек жад тұрғысынан келеді. Жылдам сұрыптау үшін қосымша жадқа қажеттілік бірнеше рекурсивті шақыруларға байланысты.

Жылдам сұрыптау алгоритмі кірістіру сұрыптау алгоритмімен салыстырғанда үлкен интеллектуалды күрделілікпен де сипатталады. Егер сіз жүз адамнан объектілер тізбегін сұрыптауды сұрасаңыз, олардың көпшілігі таңдауды сұрыптау алгоритмін қолдануы мүмкін. Сондай-ақ олардың ешқайсысының жылдам сұрыптауды қолдануы екіталай. Жылдам сұрыптаудың интеллектуалдық және кеңістіктік күрделілігінің себептері анық: алгоритм рекурсивті, оны сипаттау біршама қиын, алгоритм қарапайым сұрыптау алгоритмдеріне қарағанда ұзағырақ (бағдарлама мәтінін білдіреді).

Эй! Бүгінгі дәріс басқалардан сәл өзгеше болмақ. Ол тек Java-мен жанама түрде байланысты болуымен ерекшеленеді. Дегенмен, бұл тақырып әрбір бағдарламашы үшін өте маңызды. туралы сөйлесеміз алгоритмдер. Алгоритм дегеніміз не? Қарапайым тілмен айтқанда, бұл қажетті нәтижеге жету үшін орындалуы керек әрекеттердің кейбір тізбегі. Біз күнделікті өмірде алгоритмдерді жиі қолданамыз. Мысалы, күнде таңертең сізде тапсырма бар: мектепке немесе жұмысқа келу және сонымен бірге:

• Киінген
• таза
• толық

1. Дабылмен ояныңыз.
2. Душ қабылдаңыз, жуыңыз.
3. Таңғы ас дайындаңыз, кофе/шай қайнатыңыз.
4. Тамақ.
5. Егер сіз кешке дейін киіміңізді үтіктемеген болсаңыз, үтіктеңіз.
6. Киіну.
7. Үйден шығу.

1. Интернетте сатып алыңыз немесе жүктеп алыңыз «Орысша жеке есімдер сөздігі» 1966 жылғы басылым.
2. Осы сөздіктегі тізімнен әрбір атауды табыңыз.
3. Атау сөздіктің қай бетінде орналасқанын қағазға жазып алыңыз.
4. Қағаздағы жазбаларды пайдаланып, атауларды ретімен орналастырыңыз.

Логарифмдік күрделілік