Как стать автором
Обновить

Комментарии 16

следующий урок - возведение в степень?

Так то оператор возведения в степень ** появился в JS только в 2016 году, многие старики и не знают.

Унарный минус.

Вам бы рефераты писать за деньги. Пока читал чуть не захлебнулся.

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

Это ж надо талант иметь, чтоб такие простые вещи так непонятно объяснять.

Хотя, я не знаю, может это только в моей голове всё просто, а у других людей с другим складом ума, на самом деле требуется такое нагромождение абстракций для простых вещей?

Про деление с остатком в 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, что, может, математически и верно, но контринтуитивно.

Насчет деления трудно сказать, как интуитивнее. Если [х] округляет число вниз, то более простым кажется "всегда округлять вниз", чем "по разному в зависимости от знака". Да и Math.trunc появился недавно, а традиционным всегда был Math.floor.

Умножение двух чисел 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)).

@splincodewd

Раз уж вы процитировали мой комментарий в статье, хочу ещё кое что пояснить.

Ваши замечания:

UPD: Как хорошо подметили в комментариях, если у нас безразмерные целые числа, то понятно, что ты за один такт процессора их не сложить даже на современных процессорах.

Но если мы говорим про Int64, то это определенно O(1), а если это безразмерный Int то логарифм более похож на правду.

Если открыть учебник по матанализу за первый курс и посмотреть, что вообще такое О-большое, то нетрудно увидеть, что в его определении используется понятие предела (стремления). Например, применительно к оценке сложности алгритмов, когда говорится f(n) = O(g(n)), (где n - длина данных на входе), подразумевается поведение функции f при n стремящемся к бесконечности. Для любого конечного множества, например, для целых чисел, помещающихся в Int64, понятие О-большого не имеет смысла.

Причём, это оганичение существенно: непонятно, как распространить определение на конечное множество так, чтобы получилось что-то полезное. Например, дальше автор рассуждает про "ассимптотическую сложность" умножения и деления, но если и здесь речь про Int64, то сложность тоже в некотором смысле константная: я смогу подобрать такую константу, что умножение любых двух чисел из Int64 в неё заведомо уложится.

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

Спасибо, Вы прибавили мотивации тоже выложить свою статью на Хабре

Разработчик. Под тридцатку лет возраста. Только открыл для себя остаток от деления и решил его опробовать в JS. Поколение егэшников - это поистине чудо, потому что рационально объяснить это не представляется возможным.

Вайтишник прогуливал уроки и теперь догоняет...

Я так понимаю весь текст с упоминанием "асимптотической сложности" это гопотаЧат генеренный текст.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации