Алгоритмдик татаалдык жана динамикалык программалоо
Каалаган алгоритмдин масштабдалышын баалоо үчүн сөздүк жана жайларын тездетүүчү үч ыкма
Негизги идея: алгоритмдин наркы - секунддардын саны эмес, кириш өлчөмүнүн функциясы. O-белгилөө бул нарк кириш чоңойгон сайын кандай өсөрүн, машинанын ылдамдыгын жана туруктуу көбөйтмөлөрдү эске албай сүрөттөйт, ошондо эки алгоритмди бир сап код жазганга чейин кагазда салыштырса болот. Наркты атай билгенден кийин, аны менен күрөшсө болот: бөл да, багындыр, мемоизация жана динамикалык программалоо көптөгөн экспоненциалдык алгоритмдерди полиномдук кылат.
Аягында сиз төмөнкүлөрдү жасай аласыз:
- O-баалоолорду окуп жана жазып, эмне үчүн туруктуулар жана кичине мүчөлөр ташталарын түшүндүрүү,
- типтүү татаалдык класстарын ирээттөө жана убакыт/эстутум компромисси жөнүндө ой жүгүртүү,
- кошуп сорттоо сыяктуу алгоритмдердин артындагы «бөл да, багындыр» үлгүсүн таануу,
- экспоненциалдык рекурсияны мемоизация менен сызыктууга, андан соң ылдыйдан жогору динамикалык программалоого айландыруу.
1. Эмне үчүн секунд эмес, операцияларды санайбыз
Алгоритмди секундомер менен ченөө алгоритмдин өзүн эмес, процессоруңузду, компилятор желектерин жана бүгүнкү кэштин абалын да ченейт. Алгоритм жөнүндө өзүнчө ой жүгүртүү үчүн биз негизги операциялардын санын кириш өлчөмү n функциясы катары санап, бул сан n чоңойгондо кандай жүрөрүн сурайбыз.
Айталы, процедура 3n + 5 салыштыруу жасайт. +5 - туруктуу баштапкы чыгым, ал эми 3 - машинага көз каранды элемент боюнча туруктуу. Чоң n үчүн натыйжаны n мүчөсү чечет. Ошондуктан процедура O(n) деп айтабыз: анын убактысы сызыктуу өсөт жана киришти эки эсе көбөйтүү жумушту болжол менен эки эсе көбөйтөт.
Салыштыруу. Өлкө аркылуу жөө басуу же унаа менен баруу чечкенде, унаанын эң жогорку ылдамдыгы аралыктан кем маанилүү. Жетишерлик узун жолдо туруктуу көбөйтмө эмес, өсүштүн формасы үстөмдүк кылат. O-белгилөө форманы билдирет.