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




computer-science equality (3)

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

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

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

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


строка

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

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

чисел

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

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

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


В общем, мы используем нотацию big-O только тогда, когда n может подниматься до неприлично больших значений, потому что нотация big-O описывает, как увеличивается время выполнения при увеличении входных данных. Например, при сортировке списка большинство лучших алгоритмов сортируются по O(n log n) - это означает и означает, что когда список достаточно длинный, время, необходимое для его сортировки, пропорционально 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), а когда число становится достаточно большим, оно округляется вверх до бесконечности. И наоборот, если вы делите число снова и снова, чтобы сделать его бесконечно малым, оно в итоге округляется до нуля.


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

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





equality