PrepBro
← Назад к вопросам

Какая самая быстрая функция в алгоритмах?

2.0 Middle🔥 111 комментариев
#Python Core

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Какая самая быстрая функция в алгоритмах?

Этот вопрос можно интерпретировать несколькими способами, но обычно имеется в виду функция с лучшей асимптотической сложностью.

Сложность O(1) — константная

Самая быстрая функция с точки зрения алгоритмической сложности — это функция с O(1), которая выполняется за константное время независимо от размера входных данных:

# O(1) — одна из самых быстрых
def get_first_element(lst):
    return lst[0]  # Всегда одна операция

def is_even(n):
    return n % 2 == 0  # Всегда одна операция

def access_dict_value(d, key):
    return d[key]  # O(1) в среднем случае

def sum_two_numbers(a, b):
    return a + b  # Одна операция сложения

Время выполнения не зависит от входных данных.

Сравнение сложностей

# О(1) — константная (самая быстрая)
def const_algo(n):
    return n + 1  # Выполняется за один шаг

# 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

# O(n) — линейная
def linear_search(arr, target):
    for item in arr:
        if item == target:
            return item
    return None

# O(n log n) — логарифмическая линейная
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

# O(n²) — квадратичная
def bubble_sort(arr):
    for i in range(len(arr)):
        for j in range(len(arr) - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# O(2^n) — экспоненциальная (медленная)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Иерархия сложностей

Лучше             →  Хуже
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2^n) < O(n!)

Практический пример

Сравним скорость на списке из 1 млн элементов:

import timeit

# Создаём список
lst = list(range(1000000))

# O(1) — 0.0001 сек
time_const = timeit.timeit(lambda: lst[0], number=1000000)
print(f"O(1): {time_const:.4f}s")

# O(log n) для бинарного поиска — 0.05 сек
import bisect
time_log = timeit.timeit(
    lambda: bisect.bisect_left(lst, 500000),
    number=1000000
)
print(f"O(log n): {time_log:.4f}s")

# O(n) для линейного поиска — 50 сек
def linear_search():
    for i in lst:
        if i == 500000:
            return i

time_linear = timeit.timeit(linear_search, number=1)
print(f"O(n): {time_linear:.4f}s")

Встроенные O(1) операции в Python

# Все эти операции — O(1)
lst = [1, 2, 3, 4, 5]
lst[0]           # Доступ по индексу
lst[-1]          # Доступ к последнему
len(lst)         # Длина списка (Python кэширует это)
lst.append(6)    # Добавление в конец (амортизированное)

d = {'a': 1, 'b': 2}
d['a']           # Доступ к значению
len(d)           # Количество ключей

s = {1, 2, 3}
2 in s           # Проверка наличия в set
len(s)           # Размер set

Оптимальный алгоритм

Самый быстрый алгоритм для конкретной задачи часто невозможен, но можно оптимизировать:

# ❌ Медленно — O(n²)
def find_duplicates_slow(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

# ✅ Быстро — O(n)
def find_duplicates_fast(arr):
    seen = set()
    for num in arr:
        if num in seen:
            return True
        seen.add(num)
    return False

# ✅ Оптимально — O(n)
def find_duplicates_optimal(arr):
    return len(arr) != len(set(arr))

Примеры O(1) функций

# 1. Простая математика
def add_numbers(a, b):
    return a + b  # O(1)

# 2. Проверка условия
def is_positive(n):
    return n > 0  # O(1)

# 3. Доступ к элементу по индексу
def get_element(arr, index):
    return arr[index]  # O(1)

# 4. Словарь
def get_value(d, key):
    return d.get(key)  # O(1) в среднем

# 5. Set
def contains(s, element):
    return element in s  # O(1) в среднем

# 6. Булевые операции
def logic(a, b):
    return a and b or not a  # O(1)

Специальные случаи

Некоторые "O(1)" операции на самом деле чуть медленнее:

# Амортизированное O(1)
lst = []
for i in range(1000000):
    lst.append(i)  # Обычно O(1), но иногда O(n) при realloc

# O(1) в среднем, но O(n) в худшем
d = {}
for i in range(1000000):
    d[i] = i  # Обычно O(1), но при коллизиях может быть медленнее

Кэширование результатов

Для повторяющихся вычислений можно добиться O(1):

from functools import lru_cache

# Без кэширования — O(2^n)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

# С кэшем — O(n) для вычисления, O(1) для повторного доступа
@lru_cache(maxsize=None)
def fib_cached(n):
    if n <= 1:
        return n
    return fib_cached(n - 1) + fib_cached(n - 2)

# Вторая вызов — O(1)
print(fib_cached(100))  # O(100)
print(fib_cached(100))  # O(1) — из кэша

Итоговый ответ

Самая быстрая функция в алгоритмах — это функция со сложностью O(1) (константная).

Типичные примеры:

  • Доступ к элементу массива по индексу
  • Вычисление простого выражения
  • Доступ к значению словаря
  • Проверка наличия элемента в set

Такие операции занимают одно и то же время независимо от размера входных данных.

Какая самая быстрая функция в алгоритмах? | PrepBro