როგორ შევაფასოთ ალგორითმის სირთულე ან განვსაზღვროთ მისი ასიმპტოტა?

Алгоритмнің күрделілігін бағалау үшін, алгоритмнің тиімділігін кіріс деректерінің өлшеміне ($n$) байланысты сипаттайтын асимптотикалық талдау пайдаланылады. Негізгі қадамдар:

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

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

Әдетте, алгоритмнің ең нашар сценарийін түсіну үшін үлкен О ($O$) пайдаланылады, ол алгоритмнің масштабталуын бағалауда маңызды.

4. Константтар мен төменгі дәрежелі мүшелерді елемеу: Асимптотикалық анықтамада, константтық көбейткіштер мен төменгі дәрежелі мүшелер еленбейді, себебі үлкен $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$).