Nümunə tapşırıqların müxtəlif çətinlik səviyyələri

3.1 Sabit mürəkkəblikli məsələlər O(1).

Massivin elementinə indeks vasitəsilə daxil olmaq:

Massivin elementinə indeks vasitəsilə daxil olmaq əməliyyatı sabit vaxtda həyata keçirilir, çünki elementin ünvanı birbaşa hesablanır.

def get_element(arr, index):
    return arr[index]

Elementi siyahının əvvəlinə əlavə etmək (Deque):

İki tərəfli növbə (deque) istifadə edərək elementi siyahının əvvəlinə sabit vaxtda əlavə etmək mümkündür.

from collections import deque

def insert_element(dq, element):
    dq.appendleft(element)

3.2 Xətti mürəkkəblikli O(n) tapşırıqlar.

Massivdə xətti axtarış:

Sıralanmamış massivdə elementi tapmaq xətti vaxt tələb edir, çünki hər bir elementi yoxlamaq lazım ola bilər.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

Massivdə elementlərin sayını hesablama:

Bütün massiv elementlərinin üzərindən keçərək onların sayını hesablamaq xətti vaxt aparır.

def count_elements(arr):
    count = 0
    for element in arr:
        count += 1
    return count

3.3 Logaritmik mürəkkəblik O(log n) olan məsələlər.

İkili axtarış:

Sıralanmış massivdə elementin ikili axtarışla tapılması logaritmik vaxt alır.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Elementin ikili axtarış ağacına əlavə edilməsi:

Elementin balanslaşdırılmış ikili axtarış ağacına (BST) əlavə edilməsi logaritmik vaxt tələb edir.

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key
        
def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.val:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

3.4 Quadratik mürəkkəblikdə O(n^2) tapşırıqlar.

Bubble Sort (Baloncuk növü):

Array-in bubble sort metodu ilə növlənməsi quadratik vaxt tələb edir.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

Cüt döngü ilə dublikatların olub-olmadığını yoxlama:

Array-dakı dublikatların olub-olmadığını cüt döngü ilə yoxlama quadratik vaxt tələb edir.

def has_duplicates(arr):
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] == arr[j]:
                return True
    return False

3.5 Eksponensial mürəkkəblikli tapşırıqlar O(2^n).

Hanoi qüllələri tapşırığı:

Hanoi qüllələri tapşırığının həlli hər bir diskin yerini dəyişmək zərurətindən dolayı eksponensial vaxt tələb edir.

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Disk 1-i {source}-dən {target}-a hərəkət etdir")
        return
    hanoi(n - 1, source, auxiliary, target)
    print(f"Disk {n}-ni {source}-dən {target}-a hərəkət etdir")
    hanoi(n - 1, auxiliary, target, source)

Cəmlərin bütün alt çoxluqlarının generasiyası:

Bir çoxluğun bütün alt çoxluqlarının generasiyası eksponensial vaxt tələb edir, çünki hər bir alt çoxluq nəzərdən keçirilməlidir.

def generate_subsets(s):
    result = []
    subset = []

    def backtrack(index):
        if index == len(s):
            result.append(subset[:])
            return
        subset.append(s[index])
        backtrack(index + 1)
        subset.pop()
        backtrack(index + 1)
        
    backtrack(0)
    return result
        
print(generate_subsets([1, 2, 3]))