3.1 Задачи с постоянной сложностью O(1)
.
Доступ к элементу массива по индексу:
Операция доступа к элементу массива по индексу выполняется за постоянное время, так как адрес элемента вычисляется напрямую.
def get_element(arr, index):
return arr[index]
Вставка элемента в начало списка (Deque):
Использование двусторонней очереди (deque) позволяет вставлять элемент в начало списка за постоянное время.
from collections import deque
def insert_element(dq, element):
dq.appendleft(element)
3.2 Задачи с линейной сложностью O(n)
.
Линейный поиск в массиве:
Поиск элемента в неотсортированном массиве выполняется за линейное время, так как может потребоваться проверка каждого элемента.
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
Подсчет количества элементов в массиве:
Проход по всем элементам массива для их подсчета занимает линейное время.
def count_elements(arr):
count = 0
for element in arr:
count += 1
return count
3.3 Задачи с логарифмической сложностью O(log n)
.
Бинарный поиск:
Поиск элемента в отсортированном массиве с помощью бинарного поиска выполняется за логарифмическое время.
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
Вставка элемента в бинарное дерево поиска:
Вставка элемента в сбалансированное бинарное дерево поиска (BST) занимает логарифмическое время.
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 Задачи с квадратичной сложностью O(n^2)
.
Сортировка пузырьком:
Сортировка массива методом пузырька выполняется за квадратичное время.
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]
Проверка на наличие дубликатов с помощью двойного цикла:
Проверка массива на наличие дубликатов с помощью двойного цикла занимает квадратичное время.
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 Задачи с экспоненциальной сложностью O(2^n)
.
Задача о Ханойских башнях:
Решение задачи о Ханойских башнях занимает экспоненциальное время из-за необходимости перемещения каждого диска.
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)
Генерация всех подмножеств множества:
Генерация всех подмножеств множества занимает экспоненциальное время, так как каждое подмножество должно быть рассмотрено.
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]))
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ