Обсуждение:Статистики на отрезках. Корневая эвристика — различия между версиями

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

Текущая версия на 16:36, 26 мая 2012

категории
мелочь, но все же когда пишут for i = a to b, это — по закрытому интервалу, так что лучше for i = 0 to n-1.
лучше один раз напиши вначале, что у тебя это все строится над ассоциативной операцией (да по идее, это даже уже есть в опеределении), а дальше не перечисляй постоянно сумма/максимум/минимум. Просто говори «операция».
нормально расписать среди каких элементов надо искать минимум, а то там какие-то левые k.
Оценку лучше для каждой операции написать отдельно, потому что, например, по не совсем удачному примеру изменения создается ощущение, что его за O(1) можно делать.
Собственно, про изменение — поменять-то надо два элемента, но это не означает O(1). При подсчете суммы просто повезло, что изменение элемента совпадает с изменением всего блока. Был бы минимум или произведение — пришлось бы заново пересчитывать всю операцию в блоке, так что лучше напиши псевдокод минимума/максимума/произведения.
«то нам необходимо поменять всего два элемента» — два элемента поменяются в обоих случаях же, просто количество операций будет разное.
Опять про два элемента. Да их в любом случае два изменится.
Опять кривая формулировка. Значение для блока мы итак пересчитываем в обеих случаях. Просто прямо там же напиши, что в первом случае мы можем за O(1), а во втором — за O(sqrt(n)).
А ты уверен, что запрос на изменение должен принимать delta? Было бы странно, так как у тебя всегда происходит прибавление, а мы как-то пытаемся абстрагироваться. Мне кажется, просто нужна замена одного элемента другим.
Ты, видимо, хотел сказать, что если есть обратная операция, можно за O(1) делать изменение? Мне кажется, это неверно, нужна еще коммутативность. Например, с умножением и ненулевыми числами, это вроде работает:
change(i, newValue):
    other = B[i / len] * inverse(A[i]) // типа деление
    A[i] = newValue
    B[i / len] = other * newValue
С произведением матриц такая штука уже, видимо, не прокатит. --Дмитрий Герасимов 10:29, 16 мая 2012 (GST)
чтобы указать границы операции min, использовать \limits\
Ну и вообще поправить всякий треш, а то тут сплошная копипаста емакса. --Дмитрий Герасимов 23:50, 6 февраля 2012 (MSK)
изменение:
в псевдокоде одном случае используется абстрактная операция [math] \circ [/math], а в другом — минимум. Используй и там и там абстрактную лучше.
Код для минимума вообще неправильный, у тебя в блоке будет всегда минимум двух его последних элементов.
почему в одном случае изменяется элемент i, а во втором — p? Пусть переменные будут одинаковые, и вообще, почитай правила оформления псевдокода и оформи весь код как функции, которые принимают индекс того, что изменить и новое значение, например (это и к остальному коду относится).
Напиши, что фича первой реализации в том, что она за O(1) может происходить, а вторая — за O(sqrt(n)).
index = len * (p / cnt) — мне кажется, ты хотел сказать index = len * (p / len), не?
«B[p / len] = A[index]; for i = index + 1 to index + len - 1; B[p / len] = B[p / len] o A[i]» — Лучше присвоить значение блока сначала нейтральному элементу, а потом нормально пробегаться по всем элементам блока. Также это к precalc относится. И к запросу.
Кстати, в таких случаях «запрос» принято переаводить не как request, а как query, и change как set. И precalc я бы переименовал в build (соответственно, «предподсчет» в «построение», у нас все-таки какая-никакая — а структура данных).