Есть много способов решить данную проблему с помощью компьютерной программы. Возьмем, к примеру, сортировку элементов в массиве, есть несколько способов сделать это. Среди распространенных примеров - сортировка слиянием, пузырьковая сортировка, сортировка вставкой, сортировка по выбору и многие другие. У всех этих алгоритмов есть свои плюсы и минусы.

Тогда перед нами встанет вопрос: какой алгоритм реализовать для решения конкретной проблемы, когда существует несколько решений указанной проблемы?

Здесь пригодится нотация Big-O. Он используется в программировании для описания сложности алгоритма. Чтобы быть более конкретным, Big-O описывает наихудший сценарий и может использоваться для описания времени выполнения или памяти, необходимой для алгоритма. путем анализа сложности различные алгоритмы, тогда мы сможем определить наиболее эффективный для реализации.

В этой статье мы кратко рассмотрим анализ алгоритмов и нотацию Big-O. Мы увидим, как можно использовать нотацию Big-O для определения сложности алгоритма с помощью различных функций Python.

Что такое нотация Big-O?

Обозначение Big-O получило свое название от «Big O» перед количеством операций. Это выражение, которое сообщает нам количество операций, которые алгоритм выполнит при выполнении программы, и позволяет нам сравнивать количество операций, выполняемых алгоритмами для выполнения определенных задач.

Сложность алгоритма

Вот некоторые из общих сложностей алгоритма и их соответствующее представление с помощью нотации Big-O:

Теперь вам может быть интересно, каково значение этих сложностей. Чтобы проиллюстрировать, как работает нотация Big-O, ниже приведены несколько примеров в Python функций, которые имеют постоянную, линейную, квадратичную и экспоненциальную сложность.

Постоянная сложность

Алгоритм постоянной сложности имеет одинаковое количество операций независимо от размера ввода (n). Возьмем, к примеру, следующий пример, где мы удваиваем значение первого элемента в списке:

def doubleFirstItem(my_list):
    my_result = my_list[0] * 2
    print(my_result)
doubleFirstItem([3, 5, 7, 9, 11])

В приведенном выше фрагменте алгоритм состоит только из 2 шагов:

1. Найдите первый элемент в списке (т.е. элемент с индексом 0) и умножьте его на 2.

2. Распечатайте результат.

Независимо от того, содержит ли список 5 элементов или 500, количество шагов, которые выполняет алгоритм, всегда одинаково. Таким образом, алгоритм имеет постоянную сложность.

Линейная сложность

Если количество операций, выполняемых алгоритмом, изменяется линейно с размером входных данных (n), говорят, что алгоритм имеет линейную сложность. Возьмем, к примеру, следующий фрагмент кода:

def sumItems(my_list):
    for item in my_list:
        sum += item
        print(sum)
sumItems([3, 5, 7, 9, 11])

В приведенном выше фрагменте for-цикл имеет такое же количество итераций, что и размер ввода (n). Поскольку список состоит из 5 элементов, цикл for выполняется 5 раз, добавляя значение каждого элемента к переменной суммы. Таким образом, мы можем видеть, что в приведенной выше функции sumItems количество итераций for-цикла равно размеру ввода (n), что означает, что он имеет линейную сложность.

Квадратичная сложность

Если количество операций, выполняемых алгоритмом, является квадратичной функцией размера входных данных (n), говорят, что алгоритм имеет квадратичную сложность. Возьмем, к примеру, следующий фрагмент кода:

def nestedForLoop(my_list):
    for item in my_list:
        for item2 in my_list:
            print(item)
nestedForLoop([3, 5, 7, 9, 11])

В приведенном выше фрагменте обратите внимание, что внешний for-цикл выполняет итерацию по всем элементам в списке, а внутренний for-цикл повторяет итерацию по каждому элементу, что приводит к общее количество операций равно n * n, где n - размер ввода (т. е. количество элементов в списке). Таким образом, говорят, что указанная выше функция имеет квадратичную сложность.

Экспоненциальная сложность

Алгоритм имеет экспоненциальную сложность, если количество выполняемых операций экспоненциально зависит от размера входных данных (n). Такие алгоритмы часто являются рекурсивными алгоритмами, которые решают проблему размера N путем рекурсивного решения двух меньших задач размера N-1. Возьмем, к примеру, приведенный ниже фрагмент кода:

def Fibonacci(num):
    if num < 0:
        print("Invalid input")
    elif n == 0 or n == 1:
        return num
    else:
        return Fibonacci(num-1) + Fibonacci(num-2)
print(Fibonacci(24))

Выше приведена наивная рекурсивная функция для вычисления числа Фибоначчи Nᵗʰ и пример функции с экспоненциальной сложностью.

Сложность наихудшего случая

Сложность алгоритма не фиксирована. Он варьируется от лучшего до наихудшего сценария. Взгляните на следующий фрагмент:

def my_search(my_key, my_list):
    for item in my_list:
        if item == my_key:
            return my_list.index(item)
    return(“Key not found”)
print(my_search(2401, [2401, 2402, 2403, 2404]))

В приведенном выше фрагменте функция my_search принимает число (my_key) и список чисел (my_list) в качестве входных данных. Он просматривает список и проверяет, соответствует ли какой-либо элемент в списке ключу. Если элемент, соответствующий ключу, найден, он возвращает индекс указанного элемента. Однако, если после каждой итерации цикла for не найдено ни одного элемента, соответствующего ключу, возвращается сообщение «Ключ не найден».

Лучшим сценарием для вышеуказанной функции будет тот, который проиллюстрирован выше, где ключ соответствует первому элементу в списке. Это приводит к сложности O (1).

Однако, если ни один элемент не соответствует ключу или если последний элемент соответствует ключу, тогда цикл for должен был пройти каждую итерацию, прежде чем выполнение функции будет завершено. Это наихудший сценарий со сложностью O (n).

При этом, когда кто-то спрашивает вас о сложности алгоритма, они часто будут интересоваться только сложностью худшего случая.

Космическая сложность

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

Чтобы лучше понять, обратитесь к примеру ниже:

def doubleNum(my_list):
    double_list = [] 
    for item in my_list:
        double_list.append(item*2)
    return double_list
list_of_nums = [1,2,3,4,5]
print(doubleNum(list_of_nums))

В приведенном выше сценарии функция doubleNum принимает список целых чисел и возвращает список, в котором все элементы были удвоены. Обратите внимание: поскольку каждый элемент во входном списке имеет соответствующий элемент в новом списке, алгоритм должен выделить память для того же количества элементов, что и во входном списке. Следовательно, пространственная сложность алгоритма становится O (n).

Нотации Big-O общих алгоритмов

Важно отметить, что не существует единого алгоритма, который был бы самым быстрым во всех случаях, поскольку нет стандартного способа ввода данных в программу. Среди распространенных алгоритмов, используемых для поиска и сортировки, рейтинг Big-O, равный O (nlog (n)), в целом является наиболее оптимальным из возможных. Некоторые алгоритмы, которые выполняются с этим рейтингом, включают быструю сортировку, сортировку слиянием и сортировку кучи. Не вдаваясь в подробности, приведенное ниже изображение иллюстрирует сложность некоторых распространенных алгоритмов наихудшего случая.

Последние мысли

Эта статья призвана помочь вам понять концепцию нотации Big-O и сложности алгоритмов. Хотя Big-O, безусловно, представляет собой нечто большее, чем я описал, вам должно быть намного легче понять более глубокие элементы сложности алгоритмов.

Если у вас есть какие-либо вопросы, пожалуйста, оставьте комментарий ниже.