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

Что быстрее O(n) или O(log(n))?

2.0 Middle🔥 81 комментариев
#Python Core#Soft Skills#Архитектура и паттерны

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

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

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

Анализ сложности: O(n) vs O(log n)

Быстрый ответ

O(log n) всегда быстрее O(n). Логарифмическая сложность означает, что операция выполняется намного меньше раз при увеличении размера входных данных.

Наглядное сравнение

import math

# Для массива из 1 000 000 элементов
n = 1_000_000

linear = n                    # 1,000,000 операций
logarithmic = math.log2(n)    # ~20 операций

print(f"O(n) операций: {linear}")
print(f"O(log n) операций: {logarithmic}")
print(f"Разница: {linear / logarithmic:.0f}x раз")

# Выход:
# O(n) операций: 1000000
# O(log n) операций: 19.93
# Разница: 50128x раз

Графическое представление

n = 10:        O(n)=10      vs  O(log n)=3.3
n = 100:       O(n)=100     vs  O(log n)=6.6
n = 1000:      O(n)=1000    vs  O(log n)=10
n = 1000000:   O(n)=1000000 vs  O(log n)=20

С ростом n разница становится астрономической.

Примеры O(log n): бинарный поиск

def binary_search(arr, target):
    """Поиск элемента в отсортированном массиве — O(log n)"""
    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

# Даже в массиве из 1 млн элементов максимум 20 операций
data = list(range(1_000_000))
result = binary_search(data, 999_999)
print(f"Найден индекс: {result}")

Примеры O(n): линейный поиск

def linear_search(arr, target):
    """Поиск элемента перебором — O(n)"""
    for i, element in enumerate(arr):
        if element == target:
            return i
    return -1

# На массиве из 1 млн элементов может быть 1 млн операций
data = list(range(1_000_000))
result = linear_search(data, 999_999)  # Худший случай — 1 млн итераций
print(f"Найден индекс: {result}")

Реальный тест производительности

import time
import math

def time_binary_search(n):
    """Время бинарного поиска"""
    arr = list(range(n))
    target = n - 1  # Худший случай
    
    start = time.perf_counter()
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            break
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return time.perf_counter() - start

def time_linear_search(n):
    """Время линейного поиска"""
    arr = list(range(n))
    target = n - 1  # Худший случай
    
    start = time.perf_counter()
    for i in range(len(arr)):
        if arr[i] == target:
            break
    return time.perf_counter() - start

# Тестирование на разных размерах
for n in [1_000, 10_000, 100_000, 1_000_000, 10_000_000]:
    log_time = time_binary_search(n)
    lin_time = time_linear_search(n)
    ratio = lin_time / log_time if log_time > 0 else float('inf')
    
    print(f"n={n:8d}: O(log n)={log_time*1e6:6.2f}μs, O(n)={lin_time*1e6:8.2f}μs, разница={ratio:.0f}x")

# Примерный результат:
# n=    1000: O(log n)=  0.10μs, O(n)=    10.50μs, разница=105x
# n=   10000: O(log n)=  0.15μs, O(n)=   110.00μs, разница=733x
# n=  100000: O(log n)=  0.20μs, O(n)=  1100.00μs, разница=5500x
# n= 1000000: O(log n)=  0.25μs, O(n)= 11000.00μs, разница=44000x

Другие примеры O(log n)

# 1. Быстрое возведение в степень
def power(x, n):
    """x^n за O(log n) вместо O(n)"""
    result = 1
    while n > 0:
        if n % 2 == 1:
            result *= x
        x *= x
        n //= 2  # Каждый раз n уменьшается в 2 раза
    return result

# 2. Поиск в бинарном дереве поиска
class BST:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
    
    def search(self, target):  # O(log n) в сбалансированном дереве
        if self.value == target:
            return self
        elif target < self.value and self.left:
            return self.left.search(target)
        elif target > self.value and self.right:
            return self.right.search(target)
        return None

# 3. Merge sort, quick sort — O(n log n)
def merge_sort(arr):
    """O(n log n) — существует n уровней, на каждом O(n) работы"""
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])      # Разделение — O(log n) уровней
    right = merge_sort(arr[mid:])     # На каждом уровне O(n) слияния
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

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

# Для n = 1,000,000:

O(1) - константная:      1 операция
O(log n) - логарифмическая:  ~20 операций (лучшее)
O(sqrt(n)) - корень:     ~1,000 операций
O(n) - линейная:         1,000,000 операций
O(n log n) - линейно-логарифмическая: ~20,000,000 операций
O(n^2) - квадратичная:   1,000,000,000,000 операций (триллион!)
O(2^n) - экспоненциальная: 2^1000000 операций (невычислимо)
O(n!) - факториальная:   (очень плохо)

Когда O(n) может быть приемлемо

# Если операция ОЧЕНЬ дешёвая, O(n) может быть быстрее O(log n)

def cheap_linear():
    """Простое сложение в цикле"""
    result = 0
    for i in range(1_000_000):
        result += i  # Очень дешёвая операция
    return result

def complex_logarithmic():
    """Сложные вычисления"""
    result = 1
    for i in range(20):  # log(1_000_000) ~ 20
        result *= expensive_function()  # Очень дорогая операция
    return result

# Несмотря на O(n) vs O(log n), cheap_linear может быть быстрее
# Потому что константные множители имеют значение!
# O(n) с маленькой константой может быть быстрее O(log n) с большой

Почему асимптотическая сложность важна

# O(n) с константой C1
time_linear = C1 * n

# O(log n) с константой C2
time_log = C2 * log(n)

# Даже если C2 > C1, для больших n время_log всегда меньше
# Потому что log(n) растёт медленнее n

C1, C2 = 1, 100  # log(n) имеет большую константу

for n in [10, 100, 1_000, 10_000, 100_000, 1_000_000]:
    t_linear = C1 * n
    t_log = C2 * math.log2(n)
    print(f"n={n:7d}: O(n)={t_linear:8.0f}ns, O(log n)={t_log:8.2f}ns")

# Выход показывает, что даже с большой константой, O(log n) выигрывает:
# n=     10: O(n)=      10ns, O(log n)=     333.22ns
# n=    100: O(n)=     100ns, O(log n)=     664.39ns
# n=   1000: O(n)=    1000ns, O(log n)=    997.24ns  <- начинает выигрывать
# n=  10000: O(n)=   10000ns, O(log n)=   1329.20ns
# n= 100000: O(n)=  100000ns, O(log n)=   1661.36ns
# n=1000000: O(n)= 1000000ns, O(log n)=   1993.28ns

Заключение

O(log n) всегда быстрее O(n) для больших данных:

  1. O(log n) — логарифмическая, растёт очень медленно
  2. O(n) — линейная, растёт пропорционально входным данным
  3. При n = 1 млн разница уже в десятки тысяч раз
  4. Используйте бинарный поиск вместо линейного где возможно
  5. Выбирайте алгоритмы с лучшей асимптотической сложностью

Правило: O(log n) > O(n) в плане производительности.