Насколько хорошо вы действительно понимаете сложность времени?

O (1) - Часть серии о Big-O

Основы

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

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

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

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

function f(array) {
  console.log("hello world");
}
f([1, 2, 3])
// => hello world
f([])
// => hello world
function random10() {
  return Math.floor(Math.random() * 10))
}
function random10()
// => returns a random integer between 0 and 9

Шпаргалка

На более практическом уровне полезно знать, что базовые операции обычно попадают в эту категорию. Вещи как:

• Основные математические операторы (+, -, *, /,%)
• Логические операции (!, ==, &&, ||)
• Назначения переменных (пусть x = 3, пусть y = «привет»)
• Поиск в индексе массива (обр. [5])
• Операции получения / установки хеш-карты (map.get («ключ»), map.set («ключ», «значение»))
• Поиск свойств (array.length, list.head, node.value…)
• Экземпляры классов (пусть c = новый круг (радиус = 5, цвет = «синий»))

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

Вот некоторые примеры:

• Связанный список append (), prepend (), head (), tail ()
• Стек push (), pop (), peek ()
• Очередь enqueue (), dequeue ()
• Узел двоичного дерева getleftChild (), getrightChild ()
• Узел графика getAdjacentNodes (узел), connectNodes (узел1, узел2)

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

Морщинка

Но такой взгляд на вещи тоже может ввести в заблуждение.

Предположим, вы хотите написать функцию, которая подсчитывает все частоты символов в строке.

Действительно простой (и эффективный) способ сделать это - перебрать в цикле все символы строки, а затем подсчитать их в хэш-карте.

function countCharacters(str) {
  let counts = {}
  for(let i = 0; i < str.length; i++) {
    let char = str[i]
    char in counts ? counts[char] += 1 : counts[char] = 1;
  }
  return counts;
}

Время выполнения этой функции зависит от длины строки. Еще 1 символ означает еще 1 шаг, поэтому время выполнения - O (N).

Но как насчет космической сложности? Мы используем несколько переменных, но очевидная переменная, которая, кажется, увеличивается вместе с размером строки, - это counts hashmap. Чем больше у вас персонажей, тем больше похоже, что вам придется отслеживать, поэтому может показаться, что это тоже O (N).

Но на самом деле это O (1), потому что вы имеете дело только с конечным набором символов.

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

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

Вопрос

Я поставлю вопрос о том, что такое постоянная временная сложность:

Что такое единство?

Это странный вопрос, но давайте подумаем, что мы имеем в виду, что означает, что что-то считается одним шагом или одной единицей памяти.

Это важная деталь, которую нужно понять, когда вы действительно начинаете погружаться в нюансы постоянной сложности времени / пространства, потому что она помогает объяснить, почему определенные операции, которые начинают выполняться в линейном времени / пространстве, на самом деле постоянны.

Возьмем действительно простой вариант: сложение целых чисел.

Цифры состоят из цифр. Количество цифр, доступных вам для составления чисел, определяет основание экспоненциальной шкалы, в которой вы будете работать. Десятичная шкала - это основание 10, потому что у нас есть десять символов для построения чисел: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Двоичный код находится в базе 2, потому что в вашем наборе есть два символа: {0, 1}.

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

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

Поскольку вы можете выполнить это преобразование оснований, это означает, что каждое число в базе 10 имеет соответствие (или отображение) 1 к 1 с каждым числом в базе 2. Модное слово - это взаимное соответствие. Обычно это просто означает, что два набора эквивалентны или, по крайней мере, имеют эквивалентное количество элементов.

Когда мы думаем о двоичном формате, мы обычно думаем о битах, которые являются фундаментальными единицами информации: ответами на вопрос «да» или «нет».

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

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

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

Это может иметь каскадный эффект, когда две цифры, которые не имеют переноса, в конечном итоге имеют одну из некоторой предыдущей суммы:

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

Так как же тогда сложение целых чисел составляет O (1)?

Ответ

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

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

Еще одна проблема, которую этот подход с ограниченным набором символов хорошо решает, - это двусмысленность.

Компьютеры в основном обрабатывают строки битов, и эти биты должны представлять что-то недвусмысленное. Например:

101101011010111011100110

Сколько цифр это означает? Это зависит от того, с чего вы начинаете и какие ограничения вы используете. Если учесть все биты, это может быть одно действительно большое число:

11906790

Или несколько меньших, если вы читаете по 8 бит за раз:

181, 174, 230

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

Отсюда и появился ASCII. Это наш конечный набор символов:

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

Хотя кажется, что с ES2020, BigInts теперь вещь:

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

Наши тела - это машины для обработки информации.

Заключение

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

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

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

Оборудование может быть меньше, быстрее, дешевле, более тщательно организовано и более энергоэффективным.

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

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

А быть хорошим инженером - значит эффективно.