Алгоритмнің күрделілігі

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

• Киінген
• Таза
• Жақсы тамақтанды

Бұл нәтижеге жетуге қандай алгоритм мүмкіндік береді?

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

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

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

Мұндай әрекеттер тізбегі біздің мәселемізді шешуге мүмкіндік береді ме? Иә, ол оған толығымен мүмкіндік береді. Бұл шешім тиімді бола ма ? Әрең. Мұнда біз алгоритмдердің тағы бір өте маңызды қасиетіне келеміз - олардың тиімділігі . Мәселені әртүрлі тәсілдермен шешуге болады. Бірақ бағдарламалауда да, күнделікті өмірде де біз ең тиімді әдісті таңдаймыз. Егер сіздің міндетіңіз сары маймен сэндвич жасау болса, сіз, әрине, бидай егіп, сиыр сауудан бастай аласыз. Бірақ бұл тиімсіз шешім болады - бұл көп уақытты қажет етеді және көп ақшаны қажет етеді. Қарапайым мәселеңізді шешу үшін сіз жай ғана нан мен май сатып ала аласыз. Ал бидай мен сиырдың алгоритмі мәселені шешуге мүмкіндік бергенімен, оны іс жүзінде қолдану үшін тым күрделі. Бағдарламалаудағы алгоритмдердің күрделілігін бағалау үшін Big-O («үлкен О») деп аталатын арнайы белгі жасалды . Big-O алгоритмнің орындалу уақыты оған берілген деректерге қаншалықты тәуелді екенін бағалауға мүмкіндік береді . Ең қарапайым мысалды қарастырайық - деректерді беру. Кейбір ақпаратты файл түрінде ұзақ қашықтыққа (мысалы, 5000 километрге) жіберу керек деп елестетіп көріңіз. Қай алгоритм ең тиімді болады? Бұл оның жұмыс істеуі керек деректерге байланысты. Мысалы, бізде көлемі 10 мегаbyte болатын аудио файл бар. Бұл жағдайда файлды Интернет арқылы тасымалдау ең тиімді алгоритм болады. Бұл бір-екі minutesты алады! Сонымен, алгоритмімізді тағы бір рет айтайық: «Егер сізге 5000 километр қашықтықтағы ақпаратты файлдар түрінде тасымалдау қажет болса, Интернет арқылы деректерді беруді пайдалану керек». Тамаша. Енді оны талдап көрейік. Бұл біздің мәселемізді шеше ме? Жалпы, иә, оны толығымен шешеді. Бірақ оның күрделілігі туралы не айта аласыз? Хмм, қазір бұл жерде қызық болады. Өйткені, біздің алгоритміміз кіріс деректерге, атап айтқанда файлдардың өлшеміне байланысты. Қазір бізде 10 мегаbyte бар және бәрі жақсы. 500 мегаbyteты тасымалдау керек болса ше? 20 гигаbyte? 500 тераbyte? 30 петаbyte? Біздің алгоритм жұмысын тоқтатады ма? Жоқ, бұл деректердің барлығын әлі де тасымалдауға болады. Аяқтау үшін ұзағырақ уақыт қажет пе? Иә, болады! Енді біз алгоритміміздің маңызды ерекшелігін білеміз: тасымалданатын деректердің өлшемі неғұрлым үлкен болса, алгоритмді аяқтау үшін соғұрлым ұзақ уақыт қажет болады . Бірақ біз бұл қатынастың қалай көрінетінін (деректер өлшемі мен оны тасымалдауға кететін уақыт арасында) дәлірек түсінгіміз келеді. Біздің жағдайда алгоритмнің күрделілігі сызықтық болады. «Сызықтық» деректер көлемі ұлғайған сайын оны беру уақыты шамамен пропорционалды түрде артады дегенді білдіреді. Егер деректер 2 есе көп болса және оны тасымалдауға 2 есе көп уақыт кетеді. Егер деректер 10 есе көп болса, тасымалдау уақыты 10 есе артады. Big-O белгісін қолданып, біздің алгоритміміздің күрделілігі O(N) ретінде анықталады . Бұл белгілеу болашақта анықтама үшін жақсы есте қалады; ол әрқашан сызықтық күрделілігі бар алгоритмдер үшін қолданылады. Назар аударыңыз: біз мұнда әртүрлі «айнымалы» нәрселер туралы мүлде сөйлеспейміз: Интернет жылдамдығы, компьютеріміздің қуаты және т.б. Алгоритмнің күрделілігін бағалау кезінде бұл жай ғана мағынасы жоқ - бәрібір біз оны басқара алмаймыз. Big-O жұмыс істеуге тура келетін «ортаға» қарамастан, алгоритмнің өзін бағалайды. Біздің мысалды жалғастырайық. Ақырында тасымалданатын файлдардың көлемі 800 тераbyte болатыны белгілі болды делік. Оларды интернет арқылы тарататын болсақ, мәселе, әрине, шешіледі. Бір ғана мәселе бар: көпшілігіміз үйімізде қолданатын стандартты заманауи сілтеме (секундына 100 мегабит) арқылы жіберу шамамен 708 күнді алады. 2 жылға жуық! :O Сонымен, біздің алгоритм бұл жерде сәйкес емес. Бізге басқа шешім керек! Кенеттен Amazon IT-гиганты көмекке келеді! Оның Amazon Snowmobile қызметі үлкен көлемдегі деректерді мобильді сақтау блоктарына жүктеп, жүк көлігімен қалаған мекенжайға жеткізуге мүмкіндік береді! Сонымен, бізде жаңа алгоритм бар! «Егер сізге ақпаратты файлдар түрінде 5000 километр қашықтықта тасымалдау қажет болса және Интернет арқылы тасымалданған кезде процесс 14 күннен астам уақытты қажет етсе, Amazon жүк көлігін пайдалану керек». Мұнда 14 күндік көрсеткіш кездейсоқ таңдалды: бұл біз көтере алатын максималды кезең делік. Алгоритмімізді талдап көрейік. Жылдамдық туралы не деуге болады? Жүк машинасы небәрі 50 км/сағ жылдамдықпен жүрсе де, ол 5000 шақырымды небәрі 100 сағатта жүріп өтеді. Бұл төрт күннен аз уақыт! Бұл Интернетті жіберу опциясынан әлдеқайда жақсы. Бұл алгоритмнің күрделілігі туралы не деуге болады? Ол сондай-ақ сызықтық бола ма, O(N)? Жоқ, болмайды. Өйткені, жүк көлігіне қанша жүк тиегеніңіз маңызды емес - ол бұрынғысынша шамамен бірдей жылдамдықпен жүреді және уақытында келеді. Бізде 800 тераbyte бар ма, әлде 10 есе көп деректер бар ма, жүк көлігі 5 күнде жетеді. Басқаша айтқанда, жүк көлігі арқылы деректерді жеткізу алгоритмі тұрақты күрделілікке ие . «Тұрақты» бұл алгоритмге берілген деректерге тәуелді емес дегенді білдіреді. Жүк көлігіне 1 ГБ флэш-диск салыңыз, ол 5 күнде келеді. Онда 800 тераbyte деректері бар дискілерді қойыңыз, ол 5 күнде келеді. Big-O пайдалану кезінде тұрақты күрделілік O(1) ретінде белгіленеді . Біз O(N) мен танысқаннан беріO(1) , енді көбірек «бағдарламашы» мысалдарын қарастырайық :) Сізге 100 саннан тұратын массив берілді делік және олардың әрқайсысын консольге басып шығару міндеті тұр. forСіз бұл тапсырманы орындайтын тұрақты цикл жазасыз

int[] numbers = new int[100];
// ..заполняем массив числами

for (int i: numbers) {
   System.out.println(i);
}

Жазбаша алгоритмнің күрделілігі қандай? Сызықтық, O(N). Бағдарлама орындауы тиіс әрекеттер саны оған қанша сан берілгеніне байланысты. Массивте 100 сан болса, 100 әрекет (экрандағы шығыс) болады.Егер массивте 10 000 сан болса, 10 000 әрекетті орындау қажет болады. Біздің алгоритмімізді жақсартуға бола ма? Жоқ. Кез келген жағдайда, біз массив арқылы N өтуін және консольге N шығуын орындауымыз керек . Басқа мысалды қарастырайық.

public static void main(String[] args) {

   LinkedList<Integer> numbers = new LinkedList<>();
   numbers.add(0, 20202);
   numbers.add(0, 123);
   numbers.add(0, 8283);
}

Бізде бос сан бар LinkedList, оған біз бірнеше сандарды енгіземіз. LinkedListБіздің мысалға бір санды енгізу алгоритмінің күрделілігін және оның тізімдегі элементтер санына қалай тәуелді екенін бағалауымыз керек . Жауап: O(1) - тұрақты күрделілік . Неліктен? Назар аударыңыз: әр кезде біз тізімнің басына нөмір енгіземіз. Сонымен қатар, есіңізде болса, сандарды элементтерге кірістіру кезінде олар ешқайда жылжытылмайды - сілтемелер қайта анықталады (егер сіз кенеттен LinkedList қалай жұмыс істейтінін ұмытып қалсаңыз, ескі дәрістеріміздіңLinkedList біріне қараңыз ). Егер қазір тізімдегі бірінші сан сан болса және біз тізімнің басына у санын енгізсек, тек қажет: х

x.previous  = y;
y.previous = null;
y.next = x;

Бұл анықтамалық қайта анықтау үшін біз үшін қазір қанша сан бар екені маңызды емесLinkedList - кем дегенде бір, кем дегенде миллиард. Алгоритмнің күрделілігі тұрақты болады – O(1).

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

Дүрлікпеңіз! :) Егер «логарифмдік» сөзі лекцияны аяқтап, әрі қарай оқымағыңыз келсе, бірнеше minutes күтіңіз. Мұнда математикалық қиындықтар болмайды (басқа жерлерде мұндай түсіндірулер көп) және біз барлық мысалдарды «саусақпен» талдаймыз. Сіздің тапсырмаңыз 100 саннан тұратын массивтен бір нақты санды табу екенін елестетіп көріңіз. Дәлірек айтқанда, оның бар-жоғын тексеріңіз. Қажетті нөмір табылғаннан кейін іздеуді тоқтату керек және консольде «Қажетті нөмір табылды!» жазбасы көрсетілуі керек. Оның массивтегі индексі = ....» Мұндай есепті қалай шешер едіңіз? Мұнда шешім анық: біріншіден (немесе соңғысынан) бастап, массив элементтерін бір-бірден қайталау керек және ағымдағы санның қажетті санмен сәйкес келетінін тексеру керек. Тиісінше, әрекеттер саны массивтегі элементтер санына тікелей байланысты. Егер бізде 100 сан болса, онда келесі элементке 100 рет өтіп, сәйкестік үшін санды 100 рет тексеру керек. Егер 1000 сан болса, онда 1000 тексеру қадамы болады.Бұл анық сызықтық күрделілік, O(N) . Енді біз мысалға бір түсініктеме қосамыз: санды табу керек массив өсу ретімен сұрыпталған . Бұл біздің тапсырмамыз үшін бірдеңені өзгерте ме? Біз қалаған санды әлі де дөрекі күшпен іздей аламыз. Бірақ оның орнына біз белгілі екілік іздеу алгоритмін пайдалана аламыз . Суреттің жоғарғы қатарында сұрыпталған массивті көреміз. Онда біз 23 санын табуымыз керек. Сандарды қайталаудың орнына, біз жай ғана массивді 2 бөлікке бөліп, массивтегі орташа санды тексереміз. Біз 4 ұяшықта орналасқан санды тауып, оны тексереміз (суреттегі екінші қатар). Бұл сан 16, ал біз 23-ті іздейміз. Қазіргі сан аз. Бұл нені білдіреді? Барлық алдыңғы сандарды (олар 16 санына дейін орналасқан) тексерудің қажеті жоқ : олар біз іздегеннен аз болады, өйткені біздің массив сұрыпталған! Қалған 5 элементтің арасынан іздеуді жалғастырайық. Назар аударыңыз:Біз тек бір тексеру жасадық, бірақ ықтимал нұсқалардың жартысын алып тастадық. Бізде тек 5 элемент қалды. Біз қадамымызды қайталаймыз - қалған массивті қайтадан 2-ге бөліп, қайтадан ортаңғы элементті аламыз (суреттегі 3-жол). Бұл сан 56 және біз іздеген саннан үлкенірек. Бұл нені білдіреді? Біз тағы 3 опцияны алып тастаймыз - 56 санының өзі және одан кейінгі екі сан (олар сөзсіз 23-тен үлкен, өйткені массив сұрыпталған). Тексеру үшін бізде тек 2 сан қалды (суреттегі соңғы жол) - 5 және 6 жиым индекстері бар сандар. Біз олардың біріншісін тексереміз, және бұл біздің іздегеніміз - 23 саны! Оның индексі = 5! Алгоритміміздің нәтижелерін қарастырайық, содан кейін оның күрделілігін түсінеміз. (Айтпақшы, енді сіз оның неліктен екілік деп аталатынын түсінесіз: оның мәні деректерді үнемі 2-ге бөлу). Нәтиже әсерлі! Егер біз сызықтық іздеу арқылы қажетті санды іздесек, бізге 10 тексеру қажет болады, бірақ екілік іздеу арқылы біз оны 3-те жасадық! Ең нашар жағдайда, олардың саны 4 болар еді, егер соңғы қадамда бізге қажет сан бірінші емес, екінші болып шықса. Оның күрделілігі туралы не деуге болады? Бұл өте қызықты нүкте :) Екілік іздеу алгоритмі сызықтық іздеу алгоритміне (яғни, қарапайым санауға) қарағанда массивтегі элементтер санына әлдеқайда аз тәуелді. Жиымдағы 10 элементі бар сызықтық іздеуге ең көбі 10 тексеру қажет болады, ал екілік іздеуге ең көбі 4 тексеру қажет болады. Айырмашылық 2,5 есе. Бірақ 1000 элементтен тұратын массив үшін сызықтық іздеуге 1000 тексеру қажет, ал екілік іздеуге тек 10 қажет болады ! Айырмашылық қазірдің өзінде 100 есе! Назар аударыңыз:массивтегі элементтердің саны 100 есе өсті (10-нан 1000-ға дейін), ал екілік іздеуге қажетті тексерулер саны тек 2,5 есе өсті - 4-тен 10-ға дейін. Егер біз 10 000 элементке жетсек , айырмашылық одан да әсерлі болады: 10 000 сызықтық іздеуді тексереді және екілік үшін барлығы 14 тексереді . Және тағы да: элементтер саны 1000 есе өсті (10-нан 10000-ға дейін), бірақ тексерулер саны тек 3,5 есе (4-тен 14-ке дейін) өсті. Екілік іздеу алгоритмінің күрделілігі логарифмдік , немесе Big-O белгілеуінде O(log n) . Неліктен олай аталады? Логарифм – бұл көрсеткішке кері көрсеткіш. Екілік логарифм 2-нің дәрежесін есептеу үшін қолданылады. Мысалы, бізде екілік іздеу арқылы өту керек 10 000 элемент бар. Енді сіздің көз алдыңызда сурет бар және бұл үшін ең көбі 14 тексеру қажет екенін білесіз. Бірақ егер сіздің көз алдыңызда сурет болмаса және қажетті тексерулердің нақты санын есептеу керек болса ше? Қарапайым сұраққа жауап беру жеткілікті: алынған нәтиже >= тексерілетін элементтер саны болуы үшін 2 санын қандай дәрежеге көтеру керек? 10000 үшін бұл 14-ші қуат болады. 2-ден 13-ші дәрежеге дейін тым аз (8192) Бірақ 2-ден 14-ші дәрежеге = 16384 , бұл сан біздің шартымызды қанағаттандырады (ол >= массивтегі элементтер саны). Біз логарифмді таптық - 14. Бізге қанша тексеру керек! :) Алгоритмдер және олардың күрделілігі - бір лекцияға қосу үшін тым кең тақырып. Бірақ оны білу өте маңызды: көптеген сұхбаттарда сіз алгоритмдік есептерді аласыз. Теория үшін мен сізге бірнеше кітап ұсына аламын. Бастау үшін жақсы орын - « Грокинг алгоритмдері »: кітаптағы мысалдар Python тілінде жазылғанымен, кітаптың тілі мен мысалдары өте қарапайым. Жаңадан бастаушылар үшін ең жақсы нұсқа, сонымен қатар ол көлемі жағынан да аз. Неғұрлым маңызды оқу: Роберт Лафорет пен Роберт Седгвиктің кітаптары . Екеуі де Java тілінде жазылған, бұл сізге үйренуді жеңілдетеді. Өйткені, сіз бұл тілмен жақсы таныссыз! :) Жақсы математикалық білімі бар студенттер үшін ең жақсы нұсқа Томас Корманның кітабы болады . Бірақ сіз тек теорияға қанағаттанбайсыз! «Білу» != «мүмкіндік» Сіз HackerRank және Leetcode бағдарламаларында алгоритм есептерін шешуге машықтана аласыз . Ол жақтағы мәселелер тіпті Google және Facebook-те сұхбат кезінде жиі қолданылады, сондықтан сіз міндетті түрде жалықпайсыз :) Дәріс материалын бекіту үшін YouTube сайтында Big-O туралы тамаша бейне көруге кеңес беремін . Келесі дәрістерде кездескенше! :)