Ví dụ về bài toán với các cấp độ độ phức tạp khác nhau

3.1 Bài toán với độ phức tạp không đổi O(1).

Truy cập phần tử mảng theo chỉ số:

Thao tác truy cập phần tử mảng theo chỉ số được thực hiện trong thời gian không đổi, vì địa chỉ của phần tử được tính toán trực tiếp.

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

Chèn phần tử vào đầu danh sách (Deque):

Sử dụng hàng đợi hai đầu (deque) cho phép chèn phần tử vào đầu danh sách trong thời gian không đổi.

from collections import deque

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

3.2 Bài toán với độ phức tạp tuyến tính O(n).

Tìm kiếm tuyến tính trong mảng:

Tìm kiếm phần tử trong mảng chưa được sắp xếp được thực hiện trong thời gian tuyến tính, vì có khả năng cần kiểm tra từng phần tử.

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

Đếm số lượng phần tử trong mảng:

Đi qua tất cả các phần tử trong mảng để đếm chúng chiếm thời gian tuyến tính.

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

3.3 Bài toán với độ phức tạp logarit O(log n).

Tìm kiếm nhị phân:

Tìm kiếm phần tử trong mảng đã được sắp xếp bằng cách sử dụng tìm kiếm nhị phân được thực hiện trong thời gian logarit.

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

Chèn phần tử vào cây tìm kiếm nhị phân:

Chèn phần tử vào cây tìm kiếm nhị phân đã cân bằng (BST) chiếm thời gian logarit.

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 Bài toán với độ phức tạp bình phương O(n^2).

Sắp xếp nổi bọt:

Sắp xếp mảng bằng phương pháp nổi bọt được thực hiện trong thời gian bình phương.

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]

Kiểm tra sự tồn tại của bản sao bằng vòng lặp đôi:

Kiểm tra mảng xem có sự trùng lặp hay không với vòng lặp đôi được thực hiện trong thời gian bình phương.

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 Bài toán với độ phức tạp mũ O(2^n).

Bài toán tháp Hànội:

Giải quyết bài toán tháp Hànội chiếm thời gian mũ do cần di chuyển từng đĩa.

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi(n - 1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, auxiliary, target, source)

Sinh tất cả các tập con của tập hợp:

Sinh tất cả các tập con của tập hợp chiếm thời gian mũ, vì mỗi tập con phải được xem xét.

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]))