Предлагаю разобраться, как правильно оценить код с точки зрения его скорости выполнения.

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

Давайте рассмотрим, что же такое «хороший» и «плохой» алгоритм, на примере простой задачи с leetcode. 

Условие: на вход поступает массив целых чисел. На выходе необходимо вывести массив, в котором все нули расположены в конце, а остальные числа сохраняют свой порядок.

Пример

Вход: 7 0 1 15 0 0 3 9 0 25
Выход: 7 1 15 3 9 25 0 0 0 0 

«Плохое» решение:

def solution1(nums):
    i = 0
    n = len(nums)
    while i < n:
        if nums[i] == 0:
            ind = i
            for j in range(ind + 1, len(nums)):
                nums[ind], nums[j] = nums[j], nums[ind]
                ind += 1
            n -= 1
        else:
            i += 1
    return nums

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

«Хорошее» решение:

def solution2(nums):
    i = 0
    for j in range(len(nums)):
        if nums[j] != 0:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
    return nums

В основе второго решения лежит метод двух указателей, в котором nums[i] указывает на ноль. Если nums[j] не указывает на ноль, то значения указателей меняются местами, и нули перемещаются в конец массива.

Измерим время выполнения каждого алгоритма на одинаковых входных данных с помощью встроенной библиотеки timeit. Важно уточнить, что считается среднее время 1 000 000 итераций кода.

Время выполнения первого решения: 0.00000422994859999744 сек.

Время выполнения второго решения: 0.00000132772239999031 сек.

Несмотря на то, что второе решение выполнилось быстрее первого, оба алгоритма работают весьма за оптимальное время. Но что будет, если размер входных данных увеличится в 10^4 раза? Давайте проверим. На этот раз возьмем среднее арифметическое 10 итераций.

Время выполнения первого алгоритма: 84.48735556000028168455 сек.

Время выполнения второго алгоритма: 0.01210930999950505724 сек.

Легко заметить, что при масштабировании входных данных первый алгоритм резко деградировал, а второй всё также сохранил свою эффективность.

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

Допустим у нас есть три массива с одинаковым размером. Нужно написать алгоритм, который находит число 256 и выводит YES, если число есть, иначе NO

Входные данные

nums1 = [1, 3, 5, 17, 29, 10, 256]
nums2 = [1, 3, 5, 555, 17, 29, 10]
nums3 = [256, 1, 3, 5, 17, 29, 10]

def solution(nums):
    for x in nums:
        if x == 256:
            return 'YES'
    return 'NO'

Анализ трех массивов показывает, что программа с nums1 и nums2 займет больше всего времени и, соответственно, выполнит больше действий, так как искомое число в первом случае находится в конце, а во втором отсутствует. Быстрее всего выполнится код с nums3, так как 256 находится в начале массива.

Вывод: несмотря на то, что скорость выполнения при nums3 быстрее, чем при nums1 или nums2, в общем случае алгоритм описывается по наихудшему сценарию, то есть O(n) - линейная сложность.

Еще один пример квадратичной сложности

nums = [8, 1, 5, 2, 7, 4, 9, 0, 3, 6]
for x in range(len(nums)):
    nums.remove(x)

• O(1) — Доступ к элементу массива

• O(log n) — Бинарный поиск

• O(n) — Линейный проход по массиву

• O(n log n) — Быстрая сортировка

• O(n²) — Два вложенных цикла

• O(2^n) — Перебор всех подмножеств множества

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