Почему сравниваются строки 0 (n), а сравниваются числа 0 (1)?

Question

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

Это сделало бы сложность времени 0(n), где n - длина самой короткой строки.

Однако сравнение двух чисел на равенство равно 0(1),

Почему это? Разве переводчику не придется перебирать каждое число, чтобы проверить на равенство?

Answer 1

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

Поэтому при сравнении чисел у вас есть фиксированное количество бит для сравнения,Очень просто создать аппаратную схему, которая сравнивает столько битов одновременно (т.е. как «одно действие»).

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

Однако являются исключениями, поскольку существуют числа переменной длины, обычно называемые чем-то вроде BigInteger или BigDecimalкоторый будет вести себя очень похоже на String сравнение, так как это может в конечном итоге стать O (n) для сравнения двух BigDecimal значений на равенство (где n - длина BigDecimal s, а не их числовые значения).

Answer 2

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

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

Answer 3

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

С помощью строк JavaScript n действительно может быть сколь угодно большим *, поэтому мы говорим, что сравнение занимает O(n) время. Но с числами JavaScript (которые являются IEEE 754 числами с плавающей запятой двойной точности ), n имеет максимальный предел 64 - 1 для знакового бита, 11 для показателя степени и 53 для значащих цифр **. Из-за этого мы точно знаем, сколько времени, возможно, потребуется для сравнения чисел, и лучшие системы, которые у нас есть для сравнения чисел этого точного размера, более или менее работают одинаково, независимо от того, сколько из этих 64 цифр каждое число на самом делеимеет - следовательно, сравнение этих чисел в JavaScript считается O(1).

---

* Технически, существует верхний предел, потому что RAM может закончиться. Однако в языке не указан максимальный размер для строк, и часть сравнения строк O(n) доминирует во времени выполнения задолго до того, как это произойдет.

** Кстати, это означает, что числа вJavaScript не может расти бесконечно. После определенной точки они начинают выбрасывать меньшие цифры (например, числа выше 2 ^ 53 могут быть только четными, а числа выше 2 ^ 54 могут делиться только на 4), а когда число становится достаточно большим, оно округляется вверхдо бесконечности. И наоборот, если вы делите число снова и снова, чтобы сделать его бесконечно малым, оно в итоге округляется до нуля.

Answer 4

String

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

Сложность времени равна O (N), а фактическаяВремя зависит от того, сколько символов нужно отсканировать, прежде чем статистически появятся различия. Простого ответа нет, но ответ, тем не менее, очевиден; -)

Числа

, если два целых числа равны, невозможно узнать, не сравнивая все их биты. Таким образом, в случае равенства необходимое время пропорционально количеству битов (которое пропорционально log (abs (N)), если N является одним из сравнений).

Если их нет на самом делеравных, есть много случаев, все имеют отношение к реализации внутренних органов. Длинные целые числа хранятся в виде вектора «цифр» в базе степени 2. Если векторы не имеют одинаковую длину, то интервалы не равны, и это занимает постоянное время.

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