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

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

Что такое алгоритм?

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

Примеры из жизни, определяющие использование алгоритмов:

Рассмотрим часы. Мы знаем, что часы тикают, но как производитель устанавливает эти гайки и болты так, чтобы они продолжали двигаться, и каждые 60 секунд должна двигаться минутная стрелка, а каждые 60 минут должна двигаться часовая стрелка. Поэтому, чтобы решить эту проблему, за ней должен стоять алгоритм. Придумайте еще такие примеры…

Почему мы используем алгоритмы?

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

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

Сложность алгоритма определяет производительность алгоритма с точки зрения размера входных данных.

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

Сложность алгоритма — это функция f(n), которая определяет время работы и/или требуемое пространство для хранения алгоритма с точки зрения размера n входных данных.

В большинстве случаев объем памяти, требуемый алгоритмом, просто кратен размеру данных. Сложность должна относиться к времени работы алгоритма.

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

1. Лучший случай. Минимальное возможное значение f(n) называется наилучшим случаем.

2. Средний случай: ожидаемое значение f(n).

3. Наихудший случай: максимальное значение f(n) для любого ключевого возможного ввода.

В этой статье мы обсудим два типа сложностей:

  1. Временная сложность. Время, необходимое алгоритму, выраженное как функция размера задачи, называется временной сложностью алгоритма. Временная сложность программы — это количество компьютерного времени, необходимое для ее выполнения.
  2. Пространственная сложность. Пространственная сложность алгоритма — это объем памяти, необходимый для его выполнения. Всякий раз, когда код выполняется, некоторая память выделяется для написанного текста/кода, а дополнительная память выделяется для каждой переменной.

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