Мушкилии алгоритм

Салом! Лекцияи имруза аз дигарон андаке фарк мекунад. Он бо он фарқ мекунад, ки он танҳо бавосита бо Java алоқаманд аст. Аммо, ин мавзӯъ барои ҳар як барномасоз хеле муҳим аст. Мо дар бораи алгоритмҳо сӯҳбат хоҳем кард . Алгоритм чист? Ба ибораи оддӣ, ин як пайдарпаии муайяни амалҳост, ки барои ба даст овардани натиҷаи дилхоҳ бояд анҷом дода шаванд . Мо аксар вақт алгоритмҳоро дар ҳаёти ҳаррӯза истифода мебарем. Масалан, ҳар саҳар шумо бо вазифае рӯ ба рӯ мешавед: ба мактаб ё кор омадан ва дар айни замон:

• Либос
• Тоза
• Хуб сер

Кадом алгоритм ба шумо имкон медиҳад, ки ин натиҷаро ба даст оред?

1. Ба соати зангдор бедор шавед.
2. Душ гиред, рӯятонро бишӯед.
3. Наҳорӣ тайёр кунед, қаҳва/чой тайёр кунед.
4. Бихӯред.
5. Агар шумо аз шом либосҳои худро дарзмол накарда бошед, онҳоро дарзмол кунед.
6. Пӯшед.
7. Хонаро тарк кунед.

Ин пайдарпайии амалҳо ба шумо имкон медиҳад, ки натиҷаи дилхоҳ ба даст оред. Дар программасозй тамоми нуктаи кори мо доимо хал кардани масъалахо мебошад. Қисми зиёди ин вазифаҳоро бо истифода аз алгоритмҳои аллакай маълум иҷро кардан мумкин аст. Масалан, шумо бо вазифае рӯ ба рӯ мешавед: рӯйхати 100 номро дар массив ҷудо кунед . Ин масъала хеле содда аст, аммо онро бо роҳҳои гуногун ҳал кардан мумкин аст. Ин аст як роҳи ҳалли: Алгоритм барои ҷудо кардани номҳо аз рӯи алифбо:

1. Дар интернет "Луғати номҳои шахсии русӣ" нашри 1966 харед ё зеркашӣ кунед.
2. Ҳар як номро дар рӯйхати мо дар ин луғат пайдо кунед.
3. Дар варақе нависед, ки ном дар кадом саҳифаи лугат аст.
4. Бо истифода аз қайдҳо дар варақ номҳоро ба тартиб гузоред.

Оё чунин пайдарҳамии амалҳо имкон медиҳад, ки мушкor худро ҳал кунем? Бале, ин комилан имкон медиҳад. Оё ин ҳалли самаранок хоҳад буд ? Базӯр. Дар ин ҷо мо ба як хусусияти муҳими дигари алгоритм - самаранокии онҳо меоем . Масъаларо бо роҳҳои гуногун ҳал кардан мумкин аст. Аммо ҳам дар барномасозӣ ва ҳам дар ҳаёти ҳаррӯза мо усулеро интихоб мекунем, ки самараноктар бошад. Агар вазифаи шумо тайёр кардани сэндвич бо равған бошад, шумо метавонед, албатта, аз кишти гандум ва шири гов оғоз кунед. Аммо ин як роҳи ҳалли бесамар хоҳад буд - он вақти зиёдро талаб мекунад ва маблағи зиёдеро талаб мекунад. Барои ҳалли мушкилоти оддии худ, шумо метавонед танҳо нону равған харед. Ва алгоритми гандум ва гов, гарчанде ки он ба шумо имкон медиҳад, ки мушкилотро ҳал кунед, барои татбиқи он дар амал хеле мураккаб аст. Барои арзёбии мураккабии алгоритмҳо дар барномасозӣ, як аломати махсус бо номи Big-O (“big O”) сохта шуд . Big-O ба шумо имкон медиҳад, ки ҳисоб кунед, ки чӣ қадар вақти иҷрои алгоритм аз маълумоти ба он додашуда вобаста аст . Биёед соддатарин мисол - интиқоли маълумотро дида бароем. Тасаввур кунед, ки шумо бояд баъзе маълумотро дар шакли файл ба масофаи дур (масалан, 5000 километр) интиқол диҳед. Кадом алгоритм самараноктар хоҳад буд? Ин аз маълумоте, ки ӯ бояд бо он кор кунад, вобаста аст. Масалан, мо як файли аудиоии 10 мегаbyte дорем. Дар ин ҳолат, алгоритми самараноктарин интиқоли файл тавассути Интернет хоҳад буд. Он танҳо якчанд дақиқа мегирад! Пас, биёед алгоритми худро боз садо диҳем: "Агар ба шумо лозим аст, ки маълумотро дар шакли файлҳо ба масофаи 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 Пас, алгоритми мо дар ин ҷо мувофиқ нест. Ба мо як роҳи дигар лозим аст! Ногаҳон, бузургҷуссаи IT Amazon ба кӯмаки мо меояд! Хидмати 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(1) , биёед акнун бештар мисолҳои "барномасоз"-ро бубинем :) Фарз мекунем, ки ба шумо массиви 100 адад дода шудааст ва вазифа ин аст, ки ҳар яки онҳоро дар консол чоп кунед. Шумо як ҳалқаи муқаррариро менависед for, ки ин вазифаро иҷро мекунад

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

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

Мушкorи алгоритми хаттӣ чӣ гуна аст? Хатӣ, O(N). Миқдори амалҳое, ки барнома бояд иҷро кунад, аз он вобаста аст, ки чанд рақам ба он ворид карда шудааст. Агар дар массив 100 адад бошад, 100 амал (баромад дар экран) ба амал меояд. Оё алгоритми моро такмил додан мумкин аст? Не. Дар ҳар сурат, мо маҷбур мешавем, ки 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-ро фаромӯш карда бошед, ба яке аз лексияҳои кӯҳнаи мо нигаред ). Агар ҳоло рақами аввал дар рӯйхати мо рақам бошад хва мо рақами y-ро дар аввали рӯйхат дохил кунем, ҳама чиз лозим аст:

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

Барои ин азнавтаърифи истинод барои мо муҳим нест, ки ҳоло чанд рақам вуҷуд дорадLinkedList - ҳадди аққал як, ҳадди аққал як миллиард. Мушкorи алгоритм доимӣ хоҳад буд - O(1).

Мушкorи логарифмӣ

Хуруҷи воҳима! :) Агар калимаи "логарифмӣ" шуморо водор кунад, ки лексияро пӯшед ва минбаъд нахонед, якчанд дақиқа интизор шавед. Дар ин ҷо ҳеҷ мушкor математикӣ нахоҳад буд (дар дигар ҷойҳо ин гуна шарҳҳо зиёданд) ва мо ҳама мисолҳоро "дар ангуштон" таҳлил мекунем. Тасаввур кунед, ки вазифаи шумо ёфтани як рақами мушаххас дар массиви 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) зиёд шуд. Мушкorи алгоритми ҷустуҷӯи бинарӣ логарифмикӣ аст , ё дар қайди Big-O, O(log n) . Чаро ин тавр номида мешавад? Логарифм баръакси экспонентатсия мебошад. Барои ҳисоб кардани қудрати 2 логарифми дуӣ истифода мешавад. Масалан, мо 10 000 элемент дорем, ки мо бояд онҳоро бо истифода аз ҷустуҷӯи дуӣ гузарем. Акнун шумо дар пеши чашми худ тасвире доред ва шумо медонед, ки ин ҳадди аксар 14 санҷишро талаб мекунад. Аммо чӣ мешавад, агар дар пеши назари шумо тасвир вуҷуд надошта бошад ва шумо бояд шумораи дақиқи санҷишҳои заруриро ҳисоб кунед? Ба саволи оддй чавоб додан кифоя аст: раками 2-ро ба кадом кувва баланд кардан лозим аст, то ки натичаи ба дастомада >= шумораи элементхои тафтишшаванда бошад? Барои 10000 он қудрати 14-ум хоҳад буд. 2 ба қудрати 13-ум хеле хурд аст (8192) Аммо аз 2 то қудрати 14 = 16384 , ин рақам шарти моро қонеъ мекунад (он >= шумораи элементҳои массив аст). Мо логарифмро ёфтем - 14. Ин аст, ки ба мо чанд чек лозим аст! :) Алгоритмҳо ва мураккабии онҳо мавзӯъест, ки ба як лексия дохил карда намешавад. Аммо донистани он хеле муҳим аст: дар бисёр мусоҳибаҳо шумо масъалаҳои алгоритмиро мегиред. Барои назария, ман метавонам ба шумо якчанд китобро тавсия диҳам. Ҷои хубе барои оғоз ин " Алгоритмҳои Grocking " аст: гарчанде ки мисолҳо дар китоб бо Python навишта шудаанд, забон ва мисолҳои китоб хеле соддаанд. Беҳтарин вариант барои шурӯъкунандагон, ва он низ дар ҳаҷми хурд аст. Хониши ҷиддитар: китобҳои Роберт Лафорет ва Роберт Седгвик . Ҳарду дар Java навишта шудаанд, ки омӯзишро барои шумо каме осонтар мекунад. Охир, шумо бо ин забон хеле ошноед! :) Барои донишҷӯёни дорои маълумоти хуби математикӣ, беҳтарин вариант китоби Томас Корман хоҳад буд . Аммо шумо танҳо бо назария қонеъ нахоҳед шуд! “Донистан” != “қодир будан” Шумо метавонед ҳалли масъалаҳои алгоритмиро дар HackerRank ва Leetcode машқ кунед . Мушкилот аз он ҷо аксар вақт ҳатто ҳангоми мусоҳибаҳо дар Google ва Facebook истифода мешаванд, бинобар ин шумо бешубҳа дилгир намешавед :) Барои мустаҳкам кардани маводи лексия, ман ба шумо маслиҳат медиҳам, ки дар YouTube як видеои олӣ дар бораи Big-O тамошо кунед . Дар лексияҳои оянда вохӯрем! :)