Показатели эффективности алгоритмов

Вы уже знаете, что решить задачу можно различными способами. И в разных случаях может понадобиться неодинаковое количество ресурсов — например, времени. При выборе алгоритма это стоит принимать во внимание. Можно вспомнить пример о том, как добираться на работу. Что же учитывать при написании программ?
В идеале хотелось бы знать, сколько времени потребуется, чтобы алгоритм закончил работу и выдал нужный результат. Но проблема в том, что затраченное время зависит от множества аспектов: от языка программирования, от компилятора, операционной системы, процессора, от того, расположены ли данные в оперативной памяти или на диске, и от других факторов.
Хорошо бы иметь метрику, которая бы не зависела от того, кто, где и когда запускает программу. И чтобы эта метрика позволяла сравнивать разные алгоритмы между собой.
В качестве такой метрики используют вычислительную сложность. Она отражает скорость работы программы.
Измеряют вычислительную сложность в количестве выполняемых компьютером элементарных операций.
Под элементарной операцией понимают любую арифметическую операцию или операцию сравнения. Например, чтобы сложить два числа, нужна одна элементарная операция сложения.
На различные арифметические операции компьютер тратит неодинаковое количество ресурсов. Скажем, деление намного дороже сложения. Но при анализе сложности алгоритмов этим обычно пренебрегают. Скорость роста функции, описывающей зависимость количества элементарных операций от объёма входных данных, намного больше влияет на время работы алгоритма по мере увеличения объёма входных данных.
Оценить вычислительную сложность — значит найти зависимость между объёмом входных данных и числом элементарных операций, выполняемых алгоритмом.
Допустим, вы нашли мешок с монетами и хотите посчитать общую сумму денег в мешке. Сколько операций для этого нужно? Если число монет n, то n - 1 операция сложения.
image
Другой важный ресурс, помимо времени — память. Её объем на практике всегда ограничен. Нужно следить за тем, сколько её расходуется при работе программы. Для измерения этого ресурса используют пространственную сложность.
Оценить пространственную сложность — значит выяснить, как объём памяти, выделенный компьютером для работы алгоритма, меняется в зависимости от объёма входных данных.
Допустим, вы хотите найти в мешке монету максимального достоинства. Нужна ли для решения этой задачи дополнительная память? И будет ли объём затраченной памяти меняться, если монет в мешке станет больше?
Для решения задачи нужно помнить значение текущего максимума, чтобы сравнивать с ним ценность монеты на каждом следующем шаге. Будем хранить значение текущего максимума в переменной current_maximum. Под эту переменную нужно выделить память. Больше в этом алгоритме никакие данные сохранять не надо.
Вопрос: Изменится ли количество затрачиваемой дополнительной памяти при увеличении объёма входных данных?
Сложность алгоритма выражается функцией T = f(n), где n — размер входных данных, например, количество элементов в массиве для сортировки, а T(n) — количество элементарных операций в случае временной сложности или объём дополнительной памяти в случае пространственной.
Поиграем в игру и заодно потренируемся определять вычислительную сложность алгоритмов.
Загадайте число x и придумайте ещё некоторое количество чисел. Немного, примерно от 10 до 20 штук, но их должно быть чётное количество. Разбейте числа на два массива равной длины.
Нужно определить, можно ли получить число x, умножив какое-то число из первого массива на какое-то число из второго.
Напишем код функции, которая поможет найти ответ:
Скопировать кодPYTHON
def find_product(x, first_array, second_array):
    for a in first_array:            # перебираем все числа в первом массиве
        for b in second_array:       # для каждого из них перебираем всё из второго массива
            if a * b == x:
                print("Product of {} and {} found".format(a, b))
Сколько элементарных операций нужно выполнить?
В первом массиве всего n элементов. Для каждого из них вызывается цикл по элементам второго массива, в нём также n элементов. Итого, получаем n² шагов.
На каждом шаге происходит перемножение двух элементов, проверка результата на равенство искомому числу и ещё какие-то операции. Например, результат перемножения нужно записать в памяти, прежде чем сравнивать с n. Но таких операций будет немного. Всего получим с операций, где с — константа, которая несильно отличается от двух.
То есть всего будет n² шагов, и на каждом из них с операций.
В итоге получается, что временная сложность алгоритма T(n) = c × n².
Какая у этого алгоритма пространственная сложность, если массивы передаются в функцию по ссылке, то есть при передаче в функцию не создаётся их копия?
Существуют и другие показатели эффективности алгоритмов:
  • Описательная сложность. Она показывает, какое количество кода требуется для реализации алгоритма.
  • Время, затраченное на написание кода.
Но эти характеристики учитывают редко. Для них сложно придумать метрики. К тому же они не так зависят от изменения входных параметров алгоритма, как пространственная и временная сложность.
Именно временную и пространственную сложность вы будете изучать в этом курсе.
Важно, что при определении сложности алгоритма обычно рассматривают сложность в худшем случае — самое долгое время работы алгоритма для любого из возможных вариантов входных данных. Рассчитывать ресурсы нужно так, чтобы их в любом случае хватило.
В следующем уроке вы научитесь оценивать нужное для работы алгоритма количество элементарных операций и объём памяти в зависимости от объёма входных данных. Также вы узнаете об основных типах функций, которые эту зависимость описывают.
В чем измеряется вычислительная сложность алгоритмов?
Сложность алгоритма описывается функцией T = f(n). Что может выступать в качестве n?
Выберите верное утверждение:
Пространственная сложность описывает: