1679
правок
Изменения
Нет описания правки
: {{tick}} Собственно, про изменение — поменять-то надо два элемента, но это не означает O(1). При подсчете суммы просто повезло, что изменение элемента совпадает с изменением всего блока. Был бы минимум или произведение — пришлось бы заново пересчитывать всю операцию в блоке, так что лучше напиши псевдокод минимума/максимума/произведения.
:: «то нам необходимо поменять всего два элемента» — два элемента поменяются в обоих случаях же, просто количество операций будет разное.
:: : {{tick}} Опять про два элемента. Да их в любом случае два изменится.:: {{tick|ticked=1}} А ты уверен, что запрос на изменение должен принимать delta? Было бы странно, так как у тебя всегда происходит прибавление, а мы как-то пытаемся абстрагироваться. Мне кажется, просто нужна замена одного элемента другим.:: {{tick|ticked=1}}Ты, видимо, хотел сказать, что если есть обратная операция, можно за O(1) делать изменение? Мне кажется, это неверно, нужна еще коммутативность. Например, с умножением и ненулевыми числами, это вроде работает:
change(i, newValue):
other = B[i / len] * inverse(A[i]) // типа деление
: {{tick | ticked=1}} чтобы указать границы операции min, использовать \limits\
: {{tick | ticked=1}} Ну и вообще поправить всякий треш, а то тут сплошная копипаста емакса. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 23:50, 6 февраля 2012 (MSK)
: {{tick}} изменение:
:: в псевдокоде одном случае используется абстрактная операция <tex> \circ </tex>, а в другом — минимум. Используй и там и там абстрактную лучше.
:: Код для минимума вообще неправильный, у тебя в блоке будет всегда минимум двух его последних элементов.
:: почему в одном случае изменяется элемент i, а во втором — p? Пусть переменные будут одинаковые, и вообще, почитай правила оформления псевдокода и оформи весь код как функции, которые принимают индекс того, что изменить и новое значение, например (это и к остальному коду относится).
:: Напиши, что фича первой реализации в том, что она за O(1) может происходить, а вторая — за O(sqrt(n)).
:: index = len * (p / cnt) — мне кажется, ты хотел сказать index = len * (p / len), не?
