355
правок
Изменения
→Суммирование расширений
===Суммирование расширений===
Базируясь на алгоритмах сложения двух <tex>p</tex>-битных чисел, описанных выше, можно предложить алгоритмы суммирования расширений. В этой статье их будет предложено три: ExpansionSum, LinearExpansionSum и FastExpansionSum. Первый алгоритм прибавляет к m-элементному расширению n-элементное расширение за время <tex>O(mn)</tex>, в то время, как последние два алгоритма делают это за <tex>O(n + m)</tex>.
Несмотря на такое различие в асимптотике, первый алгоритм на практике может оказаться быстрее на расширениях, чей размер мал и фиксирован, потому что программные циклы могут быть полностью развернуты, а косвенные расходы времени исчезают, так как можно отказаться от использования массива). Линейные алгоритмы имеют определенные условия, при которых подобные оптимизации невозможны.
ExpansionSum и LinearExpansionSum имеют свойство, что если входные данные были неперекрывающимися (несмежными), то и на выходе мы получим расширения с соотв.свойством.
FastExpansionSum быстрее, чем LinearExpansionSum, используя шесть операций на компоненту вместо девяти, но имеет один важный недостаток: в расширении на выходе могут быть нулевые элементы, даже если в исходном расширении их не было.
