Алгоритмдин татаалдыгы

Салам! Бүгүнкү лекция башкалардан бир аз башкача болот. Бул Java менен кыйыр түрдө гана байланышкандыгы менен айырмаланат. Бирок, бул тема ар бир программист үчүн абдан маанилүү. Биз алгоритмдер жөнүндө сүйлөшөбүз . Алгоритм деген эмне? Жөнөкөй сөз менен айтканда, бул каалаган натыйжага жетүү үчүн аткарылышы керек иш-аракеттердин белгилүү ырааттуулугу . Биз күнүмдүк жашоодо алгоритмдерди көп колдонобуз. Мисалы, күн сайын эртең менен сиз бир милдетке туш болосуз: мектепке же жумушка келүү жана ошол эле учурда:

• Кийилген
• Таза
• Жакшы тойгон

Бул натыйжага жетүү үчүн кандай алгоритм мүмкүндүк берет?

1. Ойготкуч саат менен ойгонуңуз.
2. Душ кабыл ал, бетиңди жуу.
3. Эртең мененки тамакты даярдаңыз, кофе/чай даярдаңыз.
4. же.
5. Кечке чейин кийимиңизди үтүктөй элек болсоңуз, үтүктөңүз.
6. Кийинүү.
7. Үйдөн кет.

Бул иш-аракеттердин ырааттуулугу, албетте, каалаган натыйжаны алууга мүмкүндүк берет. Программалоодо биздин ишибиздин негизги максаты дайыма көйгөйлөрдү чечүү болуп саналат. Бул милдеттердин олуттуу бөлүгү буга чейин белгилүү алгоритмдерди колдонуу менен аткарылышы мүмкүн. Мисалы, сиз тапшырмага туш болдуңуз: массивдеги 100 аталыштын тизмесин сорттоо . Бул милдет абдан жөнөкөй, бирок аны ар кандай жолдор менен чечсе болот. Бул жерде бир чечим болуп саналат: Алфавиттик аттары сорттоо үчүн алгоритм:

1. Интернеттен сатып алыңыз же жүктөп алыңыз "Орусча жеке ысымдардын сөздүгү" 1966-жылдагы басылышы.
2. Бул сөздүктөн биздин тизмедеги ар бир ысымды табыңыз.
3. Аты сөздүктүн кайсы бетинде жазылганын кагазга жаз.
4. Кагаздагы жазууларды колдонуп, ысымдарды ирети менен жазыңыз.

Мындай аракеттердин ырааттуулугу биздин көйгөйүбүздү чечүүгө мүмкүнчүлүк береби? Ооба, ага толугу менен жол берет. Бул чечим натыйжалуу болобу ? Эптеп. Бул жерде биз алгоритмдердин дагы бир маанилүү касиетине келдик - алардын натыйжалуулугу . Маселени ар кандай жолдор менен чечсе болот. Бирок программалоодо да, күнүмдүк жашоодо да биз эң натыйжалуу ыкманы тандайбыз. Эгерде сиздин милдетиңиз май менен бутерброд жасоо болсо, анда, албетте, буудай эгип, уй саап баштасаңыз болот. Бирок бул натыйжасыз чечим болот - бул көп убакытты талап кылат жана көп акчаны талап кылат. Сиздин жөнөкөй көйгөйдү чечүү үчүн, сиз жөн эле нан жана май сатып алууга болот. Ал эми буудай менен уйдун алгоритми маселени чечүүгө мүмкүндүк бергени менен, аны иш жүзүндө колдонуу үчүн өтө татаал. Программалоодогу алгоритмдердин татаалдыгын баалоо үчүн 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) катары белгиленет . Биз О(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) - туруктуу татаалдык . Неге? Эскертүү: ар бир жолу биз тизменин башына сан киргизебиз. Мындан тышкары, эсиңизде болгондой, сандарды элементтерге киргизүүдө алар эч жакка жылдырылbyte - шилтемелер кайра аныкталат (эгерде сиз капысынан LinkedList кантип иштээрин унутуп калсаңыз, биздин эски лекцияларыбыздыLinkedList карап көрүңүз ). Эгерде азыр биздин тизмедеги биринчи сан сан болсо жана биз тизменин башына y санын киргизсек, болгону: х

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

Бул маалымдаманы кайра аныктоо үчүн азыр канча сан бар экени биз үчүн маанилүү эмесLinkedList - жок дегенде бир, жок дегенде миллиард. Алгоритмдин татаалдыгы туруктуу болот - O(1).

Логарифмдик татаалдык

Дүрбөлөң түшпөө! :) Эгерде “логарифмдик” деген сөз сизди лекцияны жаап, андан ары окубай калгыңыз келсе, бир-эки мүнөт күтө туруңуз. Бул жерде эч кандай математикалык кыйынчылыктар болбойт (башка жерлерде мындай түшүндүрмөлөр көп) жана биз бардык мисалдарды “бармактарда” талдап чыгабыз. Сиздин милдетиңиз 100 сандан турган массивде белгилүү бир санды табуу экенин элестетиңиз. Тагыраак айтканда, такыр бар же жок экенин текшериңиз. Керектүү номер табылганда, издөө токтотулушу керек жана консолдо “Керектүү номер табылды!” жазуусу көрсөтүлүшү керек. Анын массивдеги индекси = ....” Мындай маселени кантип чечет элеңиз? Бул жерде чечим түшүнүктүү: биринчиден (же акыркысынан) баштап массивдин элементтерин бирден кайталашыңыз керек жана учурдагы сан керектүү санга дал келээрин текшеришиңиз керек. Демек, аракеттердин саны массивдеги элементтердин санына түздөн-түз көз каранды. Эгерде бизде 100 сан бар болсо, анда кийинки элементке 100 жолу барып, дал келген санды 100 жолу текшеришибиз керек. Эгерде 1000 сан болсо, анда 1000 текшерүү кадамы болот.Бул ачык сызыктуу татаалдык, O(N) . Эми биз мисалга бир түшүндүрмө кошобуз: санды табышыңыз керек болгон массив өсүү тартибинде иреттелген . Бул биздин милдетибиз үчүн бир нерсени өзгөртөбү? Биз дагы эле катаал күч менен каалаган санды издей алабыз. Бирок биз анын ордуна белгилүү экorк издөө алгоритмин колдоно алабыз . Сүрөттүн жогорку сапта биз сорттолгон массивди көрөбүз. Анда 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 сызыктуу издөөнү текшерет жана экorк үчүн бардыгы болуп 14 текшерүү . Жана дагы: элементтердин саны 1000 эсеге (10дон 10000ге чейин) көбөйдү, бирок текшерүүлөрдүн саны 3,5 эсеге гана көбөйдү (4төн 14кө чейин). Бинардык издөө алгоритминин татаалдыгы логарифмдик , же Big-O белгилеринде O(log n) . Эмне үчүн мындай деп аталат? Логарифм – бул көрсөткүчтүн тескери көрсөткүчү. Бинардык логарифм 2нин күчүн эсептөө үчүн колдонулат. Мисалы, бизде бинардык издөө аркылуу өтүшүбүз керек болгон 10 000 элемент бар. Эми сиздин көз алдыңызда сүрөт бар жана бул үчүн эң көп дегенде 14 текшерүү керек экенин билесиз. Бирок, эгерде сиздин көз алдыңызда эч кандай сүрөт жок болсо, жана зарыл болгон текшерүүлөрдүн так санын эсептөө керекпи? Жөнөкөй суроого жооп берүү жетиштүү: алынган натыйжа >= текшерorп жаткан элементтердин саны болушу үчүн 2 санын кандай күчкө көтөрүү керек? 10000 үчүн бул 14-кубат болуп калат. 2ден 13-деңгээлге өтө аз (8192) Бирок 2ден 14кө чейин = 16384 , бул сан биздин шартыбызды канааттандырат (ал >= массивдеги элементтердин саны). Биз логарифмди таптык - 14. Бизге канча текшерүү керек! :) Алгоритмдер жана алардын татаалдыгы - бул бир лекцияга кирүү үчүн өтө чоң тема. Бирок аны билүү абдан маанилүү: көптөгөн интервьюларда сиз алгоритмдик маселелерди аласыз. Теория үчүн мен сизге бир нече китептерди сунуш кыла алам. Баштоо үчүн эң жакшы жер " Үлкөгөн алгоритмдер ": китептеги мисалдар Python тorнде жазылганы менен, китептин тor жана мисалдары абдан жөнөкөй. Баштоочу үчүн эң жакшы вариант, ошондой эле көлөмү аз. Дагы олуттуу окуу: Роберт Лафорет жана Роберт Седгвиктин китептери . Экөө тең Java тorнде жазылган, бул сиз үчүн үйрөнүүнү бир аз жеңилдетет. Анткени, сиз бул тил менен жакшы таанышсыз! :) Жакшы математикалык бorми бар студенттер үчүн эң жакшы вариант Томас Кормандын китеби болот . Бирок сиз жөн гана теорияга канааттанбайсыз! “Билүү” != “мүмкүн болуу” Сиз HackerRank жана Leetcode боюнча алгоритмдик маселелерди чечүүнү машыксаңыз болот . Ал жактагы көйгөйлөр Google жана Facebook менен маектешүү учурунда да көп колдонулат, андыктан сиз сөзсүз зерикпейсиз :) Лекциянын материалын бекемдөө үчүн мен YouTubeдан Big-O жөнүндө эң сонун видеону көрүүнү сунуштайм. Кийинки лекцияларда көрүшкөнчө! :)