Будьте осторожны с ловушками временной сложности

Напишите здесь

Видео «Билибили» также показывает это: [Видео «Билибили»][https://www.bilibili.com/video/BV16u4m1c7cU/?spm_id_from=333.999.0.0] и я думаю, что это хорошее видео, но язык у него китайский.

временная сложность

• Что означает временная сложность?

• Временная сложность — это мера того, сколько времени требуется алгоритму для работы, в зависимости от размера входных данных. Это способ описания эффективности алгоритма, который используется для сравнения различных алгоритмов и определения наиболее эффективного.

• Как рассчитать временную сложность?

• Чтобы вычислить временную сложность, нам нужно рассмотреть количество операций, выполняемых алгоритмом, как функцию размера входных данных. Самый распространенный способ измерения количества операций — это подсчет количества раз, когда выполняется определенная операция.

• Каковы распространенные ошибки при расчете временной сложности?

• 1. Не учитывая размер входных данных: если мы учитываем только количество операций, выполняемых алгоритмом, мы можем недооценить временную сложность. Например, если мы подсчитаем количество запусков цикла, но не учтем размер входных данных, то временная сложность может оказаться слишком высокой.
• 1. Не учитывая эффективность алгоритма: некоторые алгоритмы могут выполнять множество операций даже при небольшом размере входных данных, что может привести к высокой временной сложности. Например, алгоритмы сортировки, такие как пузырьковая сортировка и сортировка выбором, имеют квадратичную временную сложность, хотя им может потребоваться поменять местами только два элемента в небольшом массиве.
• 1. Не учитывая худший сценарий алгоритма: некоторые алгоритмы имеют лучший сценарий, при котором они выполняют меньше операций, чем худший сценарий. Например, алгоритмы поиска, такие как бинарный поиск, имеют лучший сценарий, когда они находят целевой элемент за логарифмическое время, но у них есть худший сценарий, когда им нужно проверить все элементы в массиве.

Давайте посмотрим несколько примеров временной сложности.

Вот вопрос:
Найдите не более 10 целых чисел в списке.

import random
ls = [random.randint(1, 100) for _ in range(n)]

Вот тестовая функция:

import time
def benchmark(func, *args) -> float:
    start = time.perf_counter()
    func(*args)
    end = time.perf_counter()
    return end - start

Решение 1. Используйте кучу

Вот решение, использующее модуль heapq:

def find_max_n(ls, n):
    import heapq
    return heapq.nlargest(n, ls)

Или пишем на языке Python:

def find_largest_n(nums, n):
    if n  max_heap[0]:
            max_heap[0] = num
            _sift_down(max_heap, 0)

    return max_heap

def _sift_down(heap, index):
    left = 2 * index   1
    right = 2 * index   2
    largest = index

    if left  heap[largest]:
        largest = left

    if right  heap[largest]:
        largest = right

    if largest != index:
        heap[index], heap[largest] = heap[largest], heap[index]
        _sift_down(heap, largest)

Решение 2. Используйте сортировку

Вот решение, использующее функцию сортировки:

def find_max_n(ls, n):
    return sorted(ls, reverse=True)[:n]

Почти всем известно, что временная сложность кучи равна O(n log k), а временная сложность функции сортировки равна O(n log n).

Похоже, что первое решение лучше второго. Но в Python это не так.

Посмотрите на окончательный код:

import time
def benchmark(func, *args) -> float:
    start = time.perf_counter()
    func(*args)
    end = time.perf_counter()
    return end - start

def find_max_n_heapq(ls, n):
    import heapq
    return heapq.nlargest(n, ls)

def find_max_n_python_heap(nums, n):
    if n  max_heap[0]:
            max_heap[0] = num
            _sift_down(max_heap, 0)

    return max_heap

def _sift_down(heap, index):
    left = 2 * index   1
    right = 2 * index   2
    largest = index

    if left  heap[largest]:
        largest = left

    if right  heap[largest]:
        largest = right

    if largest != index:
        heap[index], heap[largest] = heap[largest], heap[index]
        _sift_down(heap, largest)


def find_max_n_sorted(ls, n):
    return sorted(ls, reverse=True)[:n]

# test
import random
for n in range(10, 10000, 100):
    ls = [random.randint(1, 100) for _ in range(n)]
    print(f"n = {n}")
    print(f"Use    Heapq: {benchmark(find_max_n_heapq, ls, n)}")
    print(f"Python Heapq: {benchmark(find_max_n_python_heap, ls, n)}")
    print(f"Sorted      : {benchmark(find_max_n_sorted, ls, n)}")

Я запускаю его в Python3.11 VScode, вот результат:

n не большой

Использовать Heapq: 0.002430099993944168
Куча Pythonq: 0.06343129999004304
Отсортировано: 9.280000813305378e-05
п = 910
Используйте Heapq: 9.220000356435776e-05
Куча Pythonq: 0.07715500006452203
Отсортировано: 9.360001422464848e-05
п = 920
Используйте Heapq: 9.440002031624317e-05
Куча Pythonq: 0,06573969998862594
Отсортировано: 0,00012450001668184996
п = 930
Используйте Heapq: 9.689992293715477e-05
Куча Pythonq: 0,06760239996947348
Отсортировано: 9.66999214142561e-05
п = 940
Используйте Heapq: 9.600003249943256e-05
Куча Pythonq: 0.07372559991199523
Отсортировано: 9.680003859102726e-05
п = 950
Используйте Heapq: 9.770004544407129e-05
Куча Pythonq: 0.07306570000946522
Отсортировано: 0,00011979998089373112
п = 960
Используйте Heapq: 9.980006143450737e-05
Куча Pythonq: 0.0771204000338912
Отсортировано: 0,00022829999215900898
п = 970
Использовать Heapq: 0.0001601999392732978
Куча Pythonq: 0.07493270002305508
Отсортировано: 0,00010840001050382853
п = 980
Используйте Heapq: 9.949994273483753e-05
Куча Pythonq: 0.07698320003692061
Отсортировано: 0,00010300008580088615
п = 990
Используйте Heapq: 9.979994501918554e-05
Куча Pythonq: 0,0848745999392122
Отсортировано: 0,00012620002962648869

если n большое?

n = 10000
Использовать Heapq: 0.003642000025138259
Куча Pythonq: 9.698883199947886
Отсортировано: 0,00107999995816499
п = 11000
Использовать Heapq: 0.0014836000045761466
Куча Pythonq: 10.537632800056599
Отсортировано: 0,0012236000038683414
п = 12000
Использовать Heapq: 0.001384599949233234
Куча Pythonq: 12.328411899972707
Отсортировано: 0,0013226999435573816
п = 13000
Использовать Heapq: 0.0020017001079395413
Куча Pythonq: 15.637207800056785
Отсортировано: 0,0015075999544933438
п = 14000
Использовать Heapq: 0.0017026999266818166
Куча Pythonq: 17.298848500009626
Отсортировано: 0,0016967999981716275
п = 15000
Использовать Heapq: 0.0017773000290617347
Куча Pythonq: 20.780625900020823
Отсортировано: 0,0017105999868363142

Что я нашел и как это улучшить

Когда n велико, Sorted требует немного времени (иногда даже лучше, чем использование heapq), но Python Heapq требует много времени.

• Почему Sorted требует немного времени, а Python Heapq требует много времени?
• Поскольку sorted() — это встроенная функция Python, вы можете найти о ней официальный документ Python.

Встроенная функция работает быстрее, чем heapq, поскольку она написана на C, который является компилируемым языком.

• Как это улучшить?
• Вы можете использовать встроенную функцию sorted() вместо heapq.sort(), чтобы повысить производительность вашего кода. Функция sorted() — это встроенная функция в Python, которая реализована на C и поэтому работает намного быстрее, чем heapq.sort()

Заключение

Когда мы имеем дело с большими данными, нам следует использовать встроенную функцию вместо heapq.sort(), чтобы повысить производительность нашего кода. Мы должны опасаться ловушек временной сложности при работе с большими данными. Иногда ловушки временной сложности неизбежны, но мы должны стараться их избегать, насколько это возможно.

Обо мне

Привет, я Мэнциньюань. Я студент. Я люблю узнавать что-то новое.
Вы можете увидеть мой github: [Github MengQinYuan][https://github.com/mengqinyuan]