Сложность времени и сложность пространства

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

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

Используются два таких метода: временная сложность и пространственная сложность, которые обсуждаются ниже:

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

Чтобы вычислить временную сложность алгоритма, предполагается, что для выполнения одной операции требуется постоянное время c , а затем вычисляется общее количество операций для входной длины на N. Рассмотрим пример, чтобы понять процесс вычислений. Предположим, задача состоит в том, чтобы найти, существует ли пара (X, Y) в массиве, состоящем из N элементов, сумма которых равна Z. Простейшая идея состоит в том, чтобы рассмотреть каждую пару и проверить, удовлетворяет ли она данное условие или нет.

Псевдокод выглядит следующим образом:

int a[n];
for(int i = 0;i < n;i++)
  cin >> a[i]
  

for(int i = 0;i < n;i++)
  for(int j = 0;j < n;j++)
    if(i!=j && a[i]+a[j] == z)
       return true

return false

Ниже приведена реализация вышеуказанного подхода:

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

• Для ввода требуется N*c операций.
• Внешний цикл i цикл выполняется N раз.
• Для каждого i внутренний цикл j запускается N раз.

Таким образом, общее время выполнения равно N*c + N*N*c + c . Теперь игнорируйте члены более низкого порядка, поскольку члены более низкого порядка относительно незначительны для больших входных данных, поэтому берется только член высшего порядка (без константы), который в данном случае равен N * N. Для описания предельного поведения функции используются разные обозначения, но, поскольку берется наихудший случай, для представления временной сложности будет использоваться обозначение big-O.

Следовательно, временная сложность вышеописанного алгоритма составляет O(N ² ) . Обратите внимание, что временная сложность зависит исключительно от количества элементов в массиве A , то есть от входной длины, поэтому, если длина массива увеличится, время выполнения также увеличится.

Порядок роста — это то, как время выполнения зависит от длины ввода. В приведенном примере хорошо видно, что время выполнения квадратично зависит от длины массива. Порядок роста поможет легко вычислить время работы.

Другой пример: давайте рассчитаем временную сложность приведенного ниже алгоритма:

Это непростой случай. На первый взгляд кажется, что сложность O(N * log N) . N для цикла j и log(N) для цикла i . Но это неправильно. Давайте посмотрим, почему.

Подумайте, сколько раз будет запущен count++ .

• Когда i = N , он будет выполняться N раз.
• Когда i = N / 2 , он будет выполняться N / 2 раза.
• Когда i = N / 4 , он будет выполняться N / 4 раза.
• И так далее.

Общее количество запусков count++ равно N + N/2 + N/4+…+1= 2 * N . Таким образом, временная сложность будет O(N) .

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

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

Псевдокод выглядит следующим образом:

int freq[n];
int a[n];

for(int i = 0; i<n; i++)
{
   cin>>a[i];
   freq[a[i]]++;
}  

Ниже приведена реализация вышеуказанного подхода:

Здесь в алгоритме используются два массива длины N и переменная i , поэтому общее используемое пространство равно N * c + N * c + 1 * c = 2N * c + c , где c - единица пространства. Для многих входных данных константа c незначительна, и можно сказать, что пространственная сложность равна O(N) .

Есть также вспомогательное пространство, отличающееся от пространственной сложности. Основное отличие заключается в том, что пространственная сложность определяет общее пространство, используемое алгоритмом, а вспомогательное пространство определяет дополнительное пространство, которое используется в алгоритме помимо заданного ввода. В приведенном выше примере вспомогательное пространство — это пространство, используемое массивом freq[], поскольку оно не является частью данного ввода. Таким образом, общее вспомогательное пространство равно N * c + c , что составляет только O (N) .