Ирилтоо, издоо жана Big-O интуициясы
Эмне үчүн бир эле маселе он элементте заматта, ал эми он миллиондо катып калат
Негизги идея: алгоритмдин ылдамдыгы машинага эмес, көбүнчө кирүү маалыматы өскөндө анын жумушу кандай өсөрүнө байланыштуу. Big-O белгилөөсү ошол өсүштү сүрөттөйт. Сызыктуу издөө маалымат эки эсеге көбөйгөндө жумушту да эки эсеге көбөйтөт; экилик издөө муну дээрлик байкабайт. Өсүштү окуй билүү иштетүүдөн мурда эле кайсы ыкма чоң көлөмдө тез бойдон каларын алдын ала айтууга мүмкүндүк берет.
Аягында сиз мына буларды жасай аласыз:
- сызыктуу издөө менен экилик издөөнү ишке ашырып, кайсынысы качан колдонуларын айтуу,
- көбүк ирилтүү менен кыстаруу ирилтүүсүн жазып, аларды Python куруучу ирилтүүсү менен салыштыруу,
O(1),O(n),O(n log n)жанаO(n^2)класстарын окуу,- теорияны өлчөнгөн сандарга айландыруу үчүн
timeitколдонуу, - божомолдоп эмес, өсүш жөнүндө ой жүгүртүп туура куралды тандоо.
1. Эмне үчүн так кирүүнүн көлөмү маанилүү
Каалаган код кичинекей тизмеде тез. Кызыктуусу — кирүү миңдеген же миллиондогон элементке чейин өскөндө эмне болору. Биз алгоритмди секунд менен эмес (алар процессоруңузга көз каранды), кирүүнүн көлөмүнүн (аны n деп белгилейбиз) функциясы катары аткарган негизги кадамдардын саны менен өлчөйбүз.
Эгерде n эки эсеге көбөйгөндө кадамдар да болжол менен эки эсеге көбөйсө, өсүш сызыктуу. Эгерде n эки эсеге көбөйгөндө кадамдар төрт эсеге көбөйсө, өсүш квадраттык жана масштабда жазалайт. Big-O негизги мүчөнү гана калтырып, туруктууларды таштайт, анткени чоң n учурунда бардыгын так негизги мүчө чечет.
Башкача айтылбаса, биз эң начар учурду сүрөттөйбүз: эң көп жумуш талап кылган кирүү. Бул алгоритм бере ала турган чынчыл убада.