Алгоритмдердин татаалдыгы жана O-белгилөө
Алгоритмдин ылдамдыгын иштетүүдөн мурда баалоо: O-белгилөө жана секундасына 10⁸ амал эрежеси.
Туура жооп — олимпиадалык маселенин жарымы гана. Экинчи жарымы — убакыт лимитине батуу, адатта 1–2 секунда. Ошондуктан олимпиадачы биринчи үйрөнгөн нерсе — алгоритмдин ылдамдыгын код жазуудан МУРДА баалоо.
Ылдамдык киргизүүнүн өлчөмү n ге жараша амалдардын саны менен өлчөнөт жана O-белгилөө («о чоң» деп окулат) аркылуу жазылат:
• O(1) — константа: жооп формула боюнча;
• O(log n) — маселени экиге бөлүү: бинардык издөө;
• O(n) — маалыматты бир өтүү;
• O(n log n) — иреттөө;
• O(n²) — эки кабатталган цикл;
• O(2ⁿ) — подмножестволорду толук кыдыруу.
Башкы практикалык эреже: компьютер секундасына болжол менен 10⁸ жөнөкөй амал аткарат. Өз n маанисин татаалдыктын формуласына коюңуз — чечим өтөбү же жокпу, ошол замат билесиз.
Ар бир алгоритм канча амал талап кылат? n киргизиңиз, мисалы: 100000
1000, андан кийин 100000, андан кийин 1000000000 киргизип көрүңүз — саптарды 10⁸ эрежеси менен салыштырыңыз. n = 10⁵ болгондо O(n²) чечим эмнеге өтпөй каларын (10¹⁰ амал — жүз секунда), ал эми O(n log n) оңой өтөрүн көрөсүз.
Айырманы жандуу сезиңиз: төмөнкү программа 1ден n ге чейинки сандардын суммасын эки жол менен эсептейт — O(n) цикл менен жана O(1) формула менен. 1000000000 (миллиард) киргизип, аткарылуу убактысын караңыз: цикл байкаларлык убакыт алат, формула — заматта. Жооптор дал келет.
1000000000 киргизип салыштырыңыз: цикл байкаларлык ойлонот, формула заматта
Өз кодуңузду кантип баалоо керек:
• кабатталган циклдер көбөйтүлөт: n боюнча циклдин ичиндеги n боюнча цикл — бул O(n²);
• удаалаш блоктор кошулат жана эң чоңу алынат: O(n) + O(n log n) = O(n log n);
• константалар ыргытылат: 5n амал — баары бир O(n).
Тапшырма: үч фрагменттин татаалдыгын баалаңыз — (1) бир өтүү менен максимумду издөө; (2) элементтердин бардык түгөйлөрүн текшерүү; (3) n ар бир жолу 2ге бөлүнгөн цикл. Жооптор: O(n), O(n²), O(log n).
Тиркелген «Массив элементтеринин суммасы» маселесин чечиңиз — O(n) убакыттагы классикалык бир өтүү — жана сабакты өттүм деп белгилеңиз.