Comments 16
Когда я впервые столкнулся с оператором Modulo (%), я ничего не понял
😬. Тогда я учился в 9 классе...
шок-контент
следующий урок - возведение в степень?
Вам бы рефераты писать за деньги. Пока читал чуть не захлебнулся.
Если хотя бы абзац про целевую аудиторию вынести в самое начало (и желательно шрифтом в пол экрана), то этот текст имел бы хоть какой-то смысл
Это ж надо талант иметь, чтоб такие простые вещи так непонятно объяснять.
Хотя, я не знаю, может это только в моей голове всё просто, а у других людей с другим складом ума, на самом деле требуется такое нагромождение абстракций для простых вещей?
Про деление с остатком в js следует знать, что на отрицательном делимом оно работает неправильно (например, -1 % 3 === -1, хотя должно быть 2), и к результату надо прибавлять делитель. И как раз этот момент не был упомянут.
В JS используется вариант, когда знак остатка берётся из делителя. Он имеет свои плюсы.
Если x % y = z, то целочисленное деление [x / y] = (x - z) / y.
В JS: -1 % 3 === -1 => [-1 / 3] = (-1 + 1) / 3 = 0
Классическое деление по модулю: -1 mod 3 = 2 => [-1 / 3] = (-1 - 2) / 3 = -1, что, может, математически и верно, но контринтуитивно.
Умножение двух чисел x и y имеет линейную сложность, так как требуется выполнить x умножений
Что, простите? Даже если вы имели в виду "умножение на N = N сложений", то это все равно далеко от реальности, иначе перемножение/деление больших чисел занимало бы вечность. Деление, кстати, более сложная для процессора операция, чем умножение.
У нас есть запись вида x = y % z , которая будет эквивалентна x = x - y * (x / y)
А у вас спина белая переменные перепутались.
Обратите внимание, что на практике сложность операции взятия остатка может быть оптимизирована в зависимости от аппаратной архитектуры и используемого компилятора
Так может быть, расскажете, как на практике, а не как у вас в голове на основе мат. модели уровня 5 класса? Ведь задан контекст: браузерный JS, а иначе в этой информации не просто нет смысла, а она еще и вредит, т.к. создает ложные представления.
x + y – это простое сложение двух переменных. Вне зависимости от значений x и y, для выполнения сложения требуется одна операция. Следовательно, асимптотическая сложность этого выражения - константа O(1).
Сильное заявление, пахнет нобелевкой)
На самом деле это не так. Тот, кто умеет складывать числа в столбик знает, что для получеия суммы нужно сложить каждый разряд одного числа с тем же разрядом другого. Чтобы получить количество разрядов числа, нужно взять его логарифм. Так что сложность сложения двух чисел x и y произвольной длины - примерно O(log(x + y)).
Раз уж вы процитировали мой комментарий в статье, хочу ещё кое что пояснить.
Ваши замечания:
UPD: Как хорошо подметили в комментариях, если у нас безразмерные целые числа, то понятно, что ты за один такт процессора их не сложить даже на современных процессорах.
Но если мы говорим про Int64, то это определенно O(1), а если это безразмерный Int то логарифм более похож на правду.
Если открыть учебник по матанализу за первый курс и посмотреть, что вообще такое О-большое, то нетрудно увидеть, что в его определении используется понятие предела (стремления). Например, применительно к оценке сложности алгритмов, когда говорится f(n) = O(g(n)), (где n - длина данных на входе), подразумевается поведение функции f при n стремящемся к бесконечности. Для любого конечного множества, например, для целых чисел, помещающихся в Int64, понятие О-большого не имеет смысла.
Причём, это оганичение существенно: непонятно, как распространить определение на конечное множество так, чтобы получилось что-то полезное. Например, дальше автор рассуждает про "ассимптотическую сложность" умножения и деления, но если и здесь речь про Int64, то сложность тоже в некотором смысле константная: я смогу подобрать такую константу, что умножение любых двух чисел из Int64 в неё заведомо уложится.
Если автор статьи имел в виду, что на современных процессорах скорость сложения и умножения встроенных чисел зависит от их длины определенным образом, нужно было так и сказать, а не пользоваться математическими терминами.
Спасибо, Вы прибавили мотивации тоже выложить свою статью на Хабре
Разработчик. Под тридцатку лет возраста. Только открыл для себя остаток от деления и решил его опробовать в JS. Поколение егэшников - это поистине чудо, потому что рационально объяснить это не представляется возможным.
Вайтишник прогуливал уроки и теперь догоняет...
Я так понимаю весь текст с упоминанием "асимптотической сложности" это гопотаЧат генеренный текст.
Что такое деление по модулю в JavaScript?