Сложность пространства-времени: для неспециалистов и простых людей

Часть 2

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

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

Теперь, когда это не так, мне может быть удобно пояснить, почему я решил использовать способ объяснения, как я сделал в предыдущей статье. Если вы спешите, перейдите к «Краткому обзору».

Я считаю обучение попыткой достичь цели: понимания. То, насколько быстро разные люди реализуют эту цель, можно охарактеризовать как интеллект. Однако это может быть спорным, поскольку можно утверждать, что это только часть того, что можно считать интеллектом, может быть, просто огромная часть. Итак, говорим ли мы, что разум — это реализация цели или скорость, с которой она реализуется, или, возможно, непропорциональное сочетание того и другого? Каким бы ни был ваш ответ, я надеюсь, что он принесет вам покой.

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

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

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

Ладно, хватит с философской тарабарщиной, давайте перейдем к делу.

КРАТКИЙ ОБЗОР

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

Пространственная сложность

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

Временная сложность

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

КАК ВСЕ НАЧИНАЛОСЬ

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

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

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

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

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

Мы позволим умникам заморачиваться, почему концепция была названа именно так, и приступим к ее применению.

БОЛЬШОЕ ОБОЗНАЧЕНИЕ O

Асимптотический анализ

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

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

Нотация большого O использует математическую функцию для описания верхней границы сложности алгоритма. Например, если временная сложность алгоритма равна O(n²), это означает, что время работы алгоритма растет не быстрее, чем квадратичная функция f(n) = n² при увеличении размера входных данных n. Точно так же, если пространственная сложность алгоритма равна O(n), это означает, что объем памяти, требуемый алгоритмом, растет не быстрее, чем линейная функция f(n) = n по мере увеличения размера входных данных n.

Я чувствую, что этого достаточно, чтобы понять, кто что сделал, когда и почему. Давайте покажем код для добавления цвета в сцену.

ОБЫЧНЫЕ ОБОЗНАЧЕНИЯ БОЛЬШОЙ О И ИХ ЗНАЧЕНИЕ

O(1) — постоянная временная сложность

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

const arr = [1, 2, 3, 4, 5];
const value = arr[2]; // This operation takes O(1) time

2. O(log n) — логарифмическая временная сложность

Логарифмическая временная сложность означает, что время, необходимое для запуска алгоритма, увеличивается логарифмически с размером входных данных. Это очень эффективная временная сложность, и ее часто можно увидеть в алгоритмах, которые многократно делят ввод пополам. Примером алгоритма с временной сложностью O(log n) является алгоритм бинарного поиска. Вот пример того, как это работает.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid; // return the index where the target was found
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1; // return -1 if target was not found in the array
}

const arr = [1, 2, 3, 4, 5];
const index = binarySearch(arr, 3); // This operation takes O(log n) time

3. O(n) — линейная временная сложность

Линейная временная сложность означает, что время, необходимое для запуска алгоритма, увеличивается линейно с размером входных данных. Это обычная временная сложность для алгоритмов, которые должны просматривать каждый элемент в списке. Примером алгоритма с временной сложностью O(n) является алгоритм линейного поиска. Вот демонстрация ниже

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; // return the index where the target was found
    }
  }
  return -1; // return -1 if target was not found in the array
}

const arr = [1, 2, 3, 4, 5];
const index = linearSearch(arr, 3); // This operation takes O(n) time

4. O(n log n) — логарифмическая временная сложность

Логарифмическая временная сложность означает, что время, необходимое для запуска алгоритма, увеличивается на произведение размера входных данных и логарифма размера входных данных. Это обычная временная сложность для алгоритмов, использующих методы «разделяй и властвуй», такие как сортировка слиянием. Вот демонстрация.

function mergeSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

const arr = [5, 3, 1, 4, 2];
const sortedArr = mergeSort(arr); // This operation takes O(n log n) time

5. O(n²) — квадратичная временная сложность

Квадратичная временная сложность означает, что время, необходимое для запуска алгоритма, увеличивается квадратично с размером входных данных. Это медленная сложность, и ее часто можно увидеть в алгоритмах, которые должны сравнивать каждый элемент списка с любым другим элементом. Примером алгоритма с временной сложностью O(n²) является сортировка выбором.

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    const temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}

const arr = [5, 3, 1, 4, 2];
const sortedArr = selectionSort(arr); // This operation takes O(n^2) time

Теперь, когда это не так, давайте попробуем определить, как оценить конкретную временную сложность, применимую к данному алгоритму.

ПРОСТЫЕ ШАГИ ДЛЯ ОПРЕДЕЛЕНИЯ ВРЕМЕННОЙ СЛОЖНОСТИ АЛГОРИТМА

Вот простые шаги, чтобы выяснить временную сложность данного алгоритма

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

ПРИМЕРЫ

Алгоритм суммирования

Давайте возьмем следующий алгоритм для вычисления суммы первых n натуральных чисел:

function sum(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}

Основные операции, выполняемые этим алгоритмом, — это сложение, присваивание и сравнение, и вот анализ того, как они формируют временную сложность.

Операция присваивания: эта операция выполняется один раз, когда переменная total инициализируется значением 0.
Операция сравнения: эта операция выполняется n раза во время каждой итерации цикла for, когда значение i сравнивается с n. Операция сравнения выполняется n раз, поскольку цикл выполняется n итераций.
Операция сложения: эта операция выполняется n раз на каждой итерации цикла for, когда значение i добавляется к total. Операция сложения выполняется n раз, поскольку цикл выполняется n итераций.

Итак, в сумме имеем:

1 операция присваивания
n операций сравнения
n операций сложения

Складывая их, мы получаем:

1 + n + n = 2n + 1

Время работы можно выразить как T(n) = n + (n+1) + n. Упрощая, получаем T(n) = 2n+1. Доминирующий член в T(n) равен 2n, что дает нам временную сложность O(n).

Таким образом, временная сложность функции sum равна O(n).

2. Сортировка выбором

Вспомните функцию из квадратичной временной сложности

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    const temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}

const arr = [5, 3, 1, 4, 2];
const sortedArr = selectionSort(arr); // This operation takes O(n^2) time

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

Чтобы определить временную сложность функции selectionSort, нам нужно проанализировать количество выполненных операций как функцию размера входного массива arr.

Инициализация: Инициализация переменной i в первом цикле for занимает постоянное время, или O(1), поскольку выполняется только один раз.
Сравнение: Сравнение i < arr.length в первом цикле for выполняется n раз, где n — длина массива arr.
Инициализация minIndex: Инициализация переменной minIndex в первой строке внутреннего цикла for занимает постоянное время, или O(1), поскольку выполняется только один раз за итерацию внешнего цикла for.
Сравнение: сравнение j < arr.length во внутреннем for цикле выполняется (n-1) + (n-2) + ... + 1 раз, что эквивалентно сумме первых n-1 целых чисел. Эта сумма может быть выражена как n(n-1)/2 или O(n^2), потому что это арифметический ряд.
Сравнение и присваивание: Сравнение arr[j] < arr[minIndex] и присваивание minIndex = j во внутреннем цикле for выполняются (n-1) + (n-2) + ... + 1 раз, что эквивалентно сумме первых n-1 целых чисел. Эту сумму также можно выразить как n(n-1)/2 или O(n^2), потому что это арифметический ряд.
Перестановка: замена двух элементов массива с использованием временной переменной temp в последних трех строках внутреннего цикла for выполняется n-1 раз, поскольку остается n-1 элементов для замены после того, как ith элемент был помещен в правильное положение. Каждая операция подкачки занимает постоянное время или O (1).

Итак, в сумме имеем:

1 операция инициализации
n операций сравнения во внешнем цикле for
n² операций сравнения и присваивания во внутреннем цикле for
n-1 операций подкачки во внутреннем цикле for

Складывая их, мы получаем:

1 + n + n² + n - 1 = n² + 2n

Таким образом, общая временная сложность функции selectionSort составляет O(n^2), а это означает, что количество операций растет квадратично с размером входного массива arr.

ЗАКЛЮЧЕНИЕ

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

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

Мне нужен перерыв.

Дополнительные материалы на PlainEnglish.io.

Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter, LinkedIn, YouTube и Discord .

Заинтересованы в масштабировании запуска вашего программного обеспечения? Ознакомьтесь с разделом Схема.

Сложность пространства-времени: для неспециалистов и простых людей — Часть 2

Вопросы по теме