Получены точные по порядку квадратичные и чуть более высокие оценки сложности вычисления некоторых линейных преобразований схемами в базисе, состоящем из операции сложения и скалярных умножений на ограниченные константы, а также верхние оценки O (nlogn) для сложности вычисления в базисе.! <...>