Глубокое погружение в алгоритмы:
В своей первой статье я дал очень краткое введение в алгоритмы, их определение, характеристики, типы и их важность. В этой статье я дам углубленное объяснение.
Мы рассмотрим:
- Временная сложность
- пространственная сложность
- Асимптотические обозначения
Алгоритм считается эффективным, если он занимает меньше времени и потребляет меньше памяти. Эффективность алгоритма определяется временной сложностью и пространственной сложностью. Таким образом, знание временной и пространственной сложности позволяет нам заставить программу вести себя в требуемых оптимальных условиях. Это делает нас эффективными программистами.
Временная сложность:
Временная сложность программы — это общее время, необходимое программе для выполнения до ее завершения. Она не рассматривает общее время выполнения, а скорее дает информацию об изменении (увеличении или уменьшении) времени выполнения при увеличении или уменьшении количества операций в алгоритме.
Временная сложность алгоритма обычно выражается с помощью нотации big-0. Это асимптотическая нотация для представления временной сложности.
Временная сложность оценивается путем подсчета количества шагов, выполняемых алгоритмом для завершения его выполнения.
Базовый пример может быть таким:
Нам нужно найти квадрат любого числа n. Одним из решений может быть выполнение цикла n раз и прибавление числа n к самому себе n раз:
```
for i = 1 to n:
n = n + n
return n
```
Или мы можем просто использовать математический оператор * для нахождения квадрата:
```
return n * n
```
Для первого решения цикл будет выполняться n раз, таким образом, временная сложность будет не меньше n, и с увеличением значения n время также увеличивается.
Для второго решения время, затрачиваемое на выполнение, не зависит от значения n. Таким образом, временная сложность будет постоянной.
Вычисление временной сложности:
Отказ от ответственности: Я использовал тот же пример, что и в сегодняшнем исследовании.
Наиболее распространенным способом вычисления временной сложности является использование нотации big-0. Этот метод удаляет все константы, так что время работы может быть оценено с помощью n по мере приближения n к бесконечности.
Например:
```
statement
```
Для приведенного выше утверждения время работы не изменится в зависимости от n. Это сделает временную сложность постоянной.
```
for x in range(n):
statement
```
Временная сложность для приведенного выше алгоритма будет линейной. Время работы цикла будет прямо пропорционально n. При увеличении n увеличивается и время работы.
```
for x in range(n):
for j in range(n):
statement
```
Временная сложность для приведенного выше кода будет квадратичной. Это связано с тем, что время выполнения приведенных выше циклов пропорционально квадрату n.
Типы обозначений для временной сложности:
Для обозначения временной сложности используются следующие различные обозначения:
1. Большая нотация 0 (о)
2. Большая Ω-нотация (омега)
3. Большая тэта-нотация (тэта)
1. Большая О:представляет наихудший случай временной
сложность. Набор функций, которые растут медленнее,
или с той же скоростью, что и выражение. Он указывает
максимальное время, требуемое алгоритму для всех входных
значениях.
2. Большая Омега: представляет собой наилучший случай алгоритма.
временная сложность. Это набор функций, которые растут
быстрее, чем выражение, или с той же скоростью, что и выражение. Она
показывает минимальное время, требуемое алгоритму для
всех входных значений.
3. Большая тэта: представляет собой средний случай
временной и пространственной сложности алгоритма. Состоит из
все функции, которые лежат как в O, так и в Omega.
Теперь давайте разберемся, что такое пространственная сложность:
Пространственная сложность:
Пространственная сложность — это объем памяти, необходимый алгоритму во время его выполнения. Она включает в себя как вспомогательное пространство, так и пространство, используемое на входе. Вспомогательное пространство — это дополнительное/временное пространство, используемое алгоритмом.
Пространственная сложность = вспомогательное пространство + пространство для ввода.
Следующие компоненты алгоритма обычно требуют пространства:
1. Пространство данных: это пространство, необходимое для хранения всех
констант и переменных (включая временные
переменные).
2. Пространство инструкций: это пространство, необходимое для
хранения исполняемой версии программы.
3. Пространство среды: это пространство, используемое для хранения
информации о среде, используемой для восстановления
приостановленной функции. Например, когда функция (x) вызывает
функцию (y), переменные функции (x)
временно хранятся в системном стеке, пока
функция (y) выполняется внутри функции (x).
При расчете сложности пространства мы обычно рассматриваем только пространство данных и пренебрегаем пространством инструкций и пространством окружения.
Вычисление сложности пространства:
Чтобы рассчитать пространственную сложность, нам нужно знать объем памяти, используемый различными переменными данных, хотя он может быть разным для разных операционных систем, метод расчета один и тот же.
Давайте вычислим пространственную сложность на нескольких примерах:
Отказ от ответственности: приведенные ниже примеры скопированы из сегодняшнего исследования.
Пример 1:
```
def myFunction():
Int(a) = x + y + z
return a
```
В приведенном примере общий объем используемой памяти составляет ( 4 + 4 + 4 + 4 + 4 ) = 20 байт, поскольку все типы переменных — целые числа. Дополнительные 4 байта предназначены для возвращаемого значения.
Это постоянная пространственная сложность, поскольку требуемая память фиксирована.
Пример 2:
```
def myFunction():
int( sum( int(arr[]), int(n) ))
int(x) = 0
for i in range(n):
x = x + arr[i]
return x
```
В приведенном выше примере для arr[] требуется 4*n байт.
По 4 байта требуется для x, n и i.
Таким образом, общий объем требуемой памяти составит (4n + 12), поэтому пространственная сложность будет называться линейной пространственной сложностью.
Теперь, когда у нас есть хорошее понимание временной и пространственной сложности, мы рассмотрим стандартные способы их выражения.
Асимптотические обозначения:
Это стандартные обозначения, которые используются для выражения времени и пространства, требуемых алгоритмом. Это связано с тем, что невозможно указать точное число времени и пространства, требуемых алгоритмом.
Существует три основных типа асимптотических обозначений:
1. Большая O нотация
2. Тета-нотация
3. Омега
Большая О-нотация:
Обычно она представляет собой наихудший сценарий работы алгоритма. Она также известна как верхняя граница времени работы алгоритма. Она представляет сложность вашего кода с помощью алгебраических терминов.
Она говорит нам, что функция никогда не превысит заданное время для любого значения входного сигнала n.
Пример: рассмотрим алгоритм линейного поиска, в котором мы перебираем элементы внутри массива один за другим, чтобы найти определенное число. Наихудшим сценарием будет, если элемент находится в конце массива. Это приводит к временной сложности n, где n — общее количество элементов. Когда мы используем нотацию Big O, мы говорим, что временная сложность будет равна O(n). Это означает, что временная сложность никогда не превысит n. Это определяет верхнюю границу, то есть она может быть меньше или равна n.
Нотация Омега:
Используется для определения наилучшего сценария. Она определяет нижнюю границу. Она указывает минимальное время, необходимое для работы алгоритма.
Тета-нотация:
Временная сложность, представленная в этой нотации, — это среднее значение или диапазон, в котором будет находиться фактическое время выполнения.