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

Проблема…

НадуманнымO(log N) примером будет присвоение значения 'i',скажем, 64,в for цикл и делить его пополам на его предыдущее значение на каждой итерации. Что-то вроде этого:

В обычном мире это должно выполняться до 7 раз, то есть значение 'i' будет таким: 64, 32, 16, 8, 4, 2, 1, и когда оно скомпилируется в 0 выходим из цикла. Но вместо 7 циклов цикл выполнялся 1081 раз. Не верите мне?! Попробуйте запустить следующий фрагмент кода в консоли и убедитесь в этом сами. Я только что добавил счетчик для подсчета повторений цикла.

Но что может быть причиной этого?

Немного о Javascript…

JavaScript – это "свободно типизированный" язык, поэтому всякий раз, когда оператор или оператор ожидает определенный тип данных, JavaScript автоматически преобразует данные в этот тип. Это известно как неявное преобразование.

Давайте также запомним следующие значения, прежде чем мы продолжим. Это минимальноеи максимальноезначение и числоможет иметь в Javascript.

Рефакторинг нашего кода…

Давайте реструктурируем наш код, чтобы он «работал правильно». Все, что нам нужно сделать, это добавить метод Math.floor() следующим образом:

В результате, как и ожидалось, на выходе будет 7.

Теперь самое интересное. [Когда я вызываю веселье…]

Что странно, так это то, что мы не добавляем метод Math.floor(), поскольку вы могли заметить, что как только значение 'i' достигает 1, из-за неявного преобразования оно будет продолжать делить его. пополам, пока не достигнет наименьшего числового значения в JS, то есть 5e-324, и когда значение 'i' станет меньше этого, на на следующей итерации оно округляется до '0', когда мы выходим из цикла, потому что не может быть меньшего положительного числа, чем 5e-324.

Number.MIN_VALUE — это наименьшее положительное число (не самое отрицательное число), которое может быть представлено с точностью до числа с плавающей запятой — другими словами, число, ближайшее к 0. — MDN Web Docs

Таким образом, если мы видим, большой O этого фрагмента кода в идеале должен быть O(log N), но в нашем случае это будет O(log N + 1075).

То есть, даже если пользователь введет наименьшее положительное целое значение для i, равное 1, для завершения цикла потребуется 1075 циклов. И если пользователь вводит произвольно большое целое число, скажем, Number.MAX_VALUE, т. е. 1,7976931348623157e+308,что является странно большим числом, которое когда-либо нужно для этого примера, это приводит к 2099.(что почти равно 1075, учитывая количество циклов по отношению к значению 'i')

Обычно мы должны отбрасывать константы и любые младшие степени числа n. Но здесь, для этого единственного примера(в JS) я чувствую, что имея константу 1075 в дополнение к журналу N имеет смысл.

Или мы можем сказать, что это занимает O(log N + 1), так как 1075 циклов занимают постоянное время.

Полный пример

Спасибо, что терпели меня. :)