Алгоритмдин кыйынчылыгын кантип баалоо кылуу же анын…

Алгоритмдин кыйынчылыгын баалоо үчүн, алгоритмдин эффективдүүлүгүн кирүү маалыматтарынын өлчөмүнө ($n$) жараша сүрөттөө мүмкүнчүлүгүн камсыз кылган асимптотикалык талдоо колдонулат. Негизги кадамдар:

Негизги операцияларды аныктоо: $n$-ге маанилүү таасир эткен операцияларды тандоо (мисалы, салыштырмалар, берилгичтер, арифметикалык операциялар).
Операциялар санын эсептөө: $n$-ге жараша негизги операциялардын санын эсептөө. Бул так формула же баалоо болушу мүмкүн.
Асимптотикалык классты аныктоо: Жогорку, төмөнкү жана так асимптотикалык жүрүм-турумду сүрөттөө үчүн чоң О ($O$), Омега ($\Omega$) жана Тета ($\Theta$) белгилери колдонулат.

$O(f(n))$: Алгоритм $f(n)$ менен көбөйтүлгөн константага чейин убакытта иштейт, чоң $n$ үчүн. Бул жаман учурду сүрөттөө үчүн колдонулат.
$\Omega(f(n))$: Алгоритм $f(n)$ менен көбөйтүлгөн константадан кем эмес убакытта иштейт, чоң $n$ үчүн. Бул жакшы учурду сүрөттөө үчүн.
$\Theta(f(n))$: Алгоритм $f(n)$ менен пропорционалдуу убакытта иштейт, чоң $n$ үчүн. Бул ортачыл учурду сүрөттөө үчүн колдонулат.

Көп учурда, алгоритмдин эң жаман сценарийин түшүнүү үчүн чоң О ($O$) колдонулат, ал алгоритмдин масштабдуулугун баалоодо маанилүү.

Константтарды жана төмөнкү даражадагы мүчөлөрдү эске албоо: Асиптотикалык баалоодо, константтык көбөйтүүлөр жана төмөнкү даражадагы мүчөлөр эске алынбайт, анткени чоң $n$ үчүн, эң чоң көрсөткүчү бар функция доминанттуу болот. Мисалы, $3n^2 + 5n + 10$ үчүн асимптотика $O(n^2)$ болот.

Типтүү асимптотикалык класстар (өсүш тартиби боюнча):

$O(1)$: Константача татаалдыгы (жагдай $n$-ге көз каранды эмес).
$O(\log n)$: Логарифмикалык татаалдыгы (жагдай $n$-дин өсүшү менен өтө жай өсөт, мисалы, экилик издөө алгоритмдеринде).
$O(n)$: Линейдүү татаалдыгы (жагдай $n$-ге пропорционалдуу, мисалы, жай издөө).
$O(n \log n)$: Линей-логарифмикалык татаалдыгы (эффективдүү сорттоо алгоритмдеринде, мисалы, Quick Sort же Merge Sort).
$O(n^2)$: Квадраттык татаалдыгы (жагдай $n$-дин квадратына өсөт, мисалы, Bubble Sort).
$O(n^c)$ (c > 1): Полиномиалдык татаалдыгы.
$O(c^n)$ (c > 1): Экспоненциалдык татаалдыгы (жагдай $n$-дин өсүшү менен өтө тез өсөт, бардык мүмкүн болгон варианттарды издөөгө ылайыктуу).
$O(n!)$: Факториалдык татаалдыгы (ең жогорку класс, өтө тез өсөт).

Циклдук түзүмдөрдүн асимптотикасын аныктоо үчүн:

Жалпыланган блоктор: Блоктордун татаалдыгы кошулат. $O(A+B) = O(\max(A, B))$.
Көпкөңгөргөн циклдер: Итерция саны көбөйөт. $O(n \times m)$. Эгер $m=n$ болсо, татаалдык $O(n^2)$ болот.
Кирүү маалыматтарынын өлчөмүн азайтуу менен циклдер: Мисалы, бөлүү 2-ге ар бир итерцияда, бул логарифмикалык татаалдыка алып келет ($O(\log n)$).

Мисал:

Жай массивди издөө:

# Негизги операцияларды эсептөө (салыштыруулар, белгилөө)
# Бул учурда негизги операция - циклдеги салыштыруулар
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 белгилөө (циклден тышкары)
    for i in range(1, len(arr)): # Цикл $len(arr) - 1$ жолу иштейт
        # Цикл ичинде:
        # 1 салыштыруу (if arr[i] > max_val)
        # мүмкүн болсо 1 белгилөө (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

Эгер массивдин өлчөмү $n = \texttt{len(arr)}$, цикл $n-1$ жолу иштейт. Ар бир итерацияда константтуу операциялар аткарылат. Жалпы операциялар саны $n$ менен пропорционал. Асимптотикалык татаалдыгы: $O(n)$.

Мисал: Вставка сорттоо (Insertion Sort)

# Негизги операцияларды эсептөө
# Негизги операциялар: салыштыруулар жана белгилөө/көчүрүүлөр
def insertion_sort(arr):
    # Чыгаргыч цикл $n-1$ жолу иштейт
    for i in range(1, len(arr)):
        key = arr[i] # 1 белгилөө
        j = i - 1 # 1 белгилөө
        # Ички цикл эң жаман учурда $i$ жолу иштейт
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 белгилөө (көчүрүү)
            j -= 1 # 1 азайтуу жана 1 белгилөө
        arr[j + 1] = key # 1 белгилөө

Чыгаргыч цикл $n-1$ жолу иштейт. Эң жаман учурда (массив тескерисинче тартипте), ички цикл орто эсеп менен $i/2$ жолу (же $i$ чейин) иштейт. Бардык итерациялар боюнча ички циклдин операцияларынын жалпы саны: $1 + 2 + ... + (n-1) \approx n^2/2$. Асимптотикалык татаалдыгы: $O(n^2)$ эң жаман жана орто учурларда, $O(n)$ эң жакшы учурда (массив алдаган эмес). Баалоодо көбүнчө эң жаман учур каралат (Голям $O$).

Алгоритмдин кыйынчылыгын кантип баалоо кылуу же анын асимптотикасын аныктоо керек?