Бұл не?
Сабақтың тақырыбы — «Алгоритмнің күрделілігі». Талдап көрейік. Алгоритмнің күрделілігі — мына сұраққа жауап: деректер көбейсе, жұмыс неше есе көп болады. Досыңды сынып тізімінен және бүкіл қаланың тізімінен іздеп жатырсың деп елестет: іздеудің бір тәсілі баяуламайтынға жақын, ал екіншісі сағаттарға созылады. Күрделілік міндет өскенде алгоритмнің өзін қалай ұстайтынын көрсетеді.
Бұл не үшін керек?
Қазіргі жүйелер алып көлемдермен жұмыс істейді: іздеу жүйелері миллиардтаған бетті қарап шығады, жүргізушісіз көліктердегі навигаторлар секундтың үлесінде маршруттарды іріктейді, ал дата-орталықтарда нейрондық желілерді оқыту электр қуатына орасан зор ақша жұмсайды. Егер алгоритм квадраттық болса, үлкен көлемде ол жай ғана үлгермейді, және ешқандай суперкомпьютер құтқармайды. Жасанды интеллект жұмыс істейтін бағдарлама жаза алады, бірақ күрделілікті түсінетін адам оның миллион пайдаланушыда күйреп қалатынын бірден көріп, міндетті дұрыс қояды. Бұл дағдыны үлкен сервистер жасайтын кез келген командада бағалайды.
Бұл қалай жұмыс істейді?
Біз секундтарды өлшемейміз, деректер көлемі эн болғанда ең нашар жағдайда алгоритм неше қадам жасайтынын санаймыз. Сызықтық іздеу элементтерді қатарынан тексереді, сондықтан жұмыс деректермен бірге өседі. Екілік іздеу әр жолы жартысын алып тастайды, және деректерді екі есе көбейту небәрі бір салыстыруды қосады. Ал көпіршік әр жұпты дерлік салыстырады, сондықтан деректер он есе көп болса — жұмыс жүз есе көп болады; эн кішкентай болғанда айырмашылық көрінбейді, бірақ миллион элементте ол тұңғиыққа айналады.
Аздап тарих
«О үлкен» белгісін бағдарламашылар емес, он тоғызыншы ғасырдың соңындағы математиктер ойлап тапты: оны неміс математигі Пауль Бахман енгізді, ал кеңінен таратқан Эдмунд Ландау болды. Бағдарламалауға бұл тілді әйгілі көп томдық «Бағдарламалау өнері» кітабының авторы Дональд Кнут әкелді — содан бері бүкіл әлемде алгоритмдерді осылай салыстырады.
Формула: жұмыстың өсуі
Алгоритмдерді салыстыру үшін операциялар санының эн деректер көлеміне қалай тәуелді екенін жазады. Сызықтық іздеу — о эн: деректер он есе көп болса, жұмыс та он есе көп болады. Екілік іздеу — о логарифм эн: екі негізді логарифм санды неше рет екіге бөлуге болатынын көрсетеді, сондықтан деректерді екі есе көбейткенде небәрі бір салыстыру қосылады; дәлірек айтқанда, ол эннің екі негізді логарифмінің бүтін бөлігіне бір қосқан санды салыстыру жасайды. Көпіршік — о эн квадрат: әр элемент басқасының әрқайсысымен дерлік салыстырылады, және эн он есе өскенде жұмыс жүз есе өседі. Мұндағы эн — элементтер саны, өлшемсіз сан, ал нәтиже — операциялар саны.
O(n), O(log n), O(n²)n — деректер элементтерінің саны, —
O — ең нашар жағдайдағы операциялар санының өсу реті, —бинарный поиск: ⌊log₂ n⌋ + 1 сравненийn — элементтер саны, —
log₂ n — n санын неше рет екіге бөлуге болатыны, —
Формула: салыстырулар саны
Көпіршік неге эн көбейту эн минус бірді екіге бөлгенге тең салыстыру жасайды? Бірінші өту эн минус бір жұп көршіні салыстырады, келесісі біреуге аз, содан кейін тағы біреуге аз, және солай бір жұпқа дейін. Осы баспалдақты қоссақ, дәл эн көбейту эн минус бірдің жартысы шығады — бұл эн элементтен құрастыруға болатын барлық жұптың санымен бірдей. Эн әрпі — элементтер саны, жауап — салыстырулар саны, екеуі де өлшемсіз. Эн-ді екі есе арттырсақ, салыстырулар шамамен төрт есе көбейеді, өйткені мұнда эн іс жүзінде квадратта тұр. Көпіршіктің шектеуге сыятынын тексеру үшін теңсіздік құрады: эн көбейту эн минус бірдің жартысы мыңнан аспайды.
сравнений = n(n − 1)/2n — тізімдегі элементтер саны, —n(n − 1)/2 ≤ 1000n — элементтер саны, —
1000 — салыстырулар шегі, —
Практикада не істейміз?
Ал енді практикалық тапсырманы орындап көрейік. Алдыңда график тұр: көлденеңінен — эн элементтер саны, тігінен — салыстырулар саны, ал үш сызық сызықтық іздеуді, екілік іздеуді және көпіршікті көрсетеді; үзік сызықпен мың салыстыру шегі белгіленген. Қазір эн онға тең: сызықтық іздеу он салыстыру, екілік іздеу төрт, ал көпіршік қырық бес салыстыру жасайды — әзірге ол шекке оңай сыяды. Сенің міндетің — көпіршік әлі мыңнан аспайтын ең үлкен эн-ді табу. Эн көбейту эн минус бірдің жартысы мыңнан аспайды деген теңсіздік құр, эн-нің шамамен мәнін бағала да, көрші мәндерді тексер — біреуі сыюы керек, ал келесісі енді сыймайды. Егер бірдеңе түсініксіз болып қалса — ештеңе етпейді, менен кез келген нәрсені сұра, мен жауап беремін. Уайымдама.