Изменения

И сразу несколько обламываемся из-за природы ловим 2 облома: Первый: природа коэффициентов разложения — распределение похоже на нормальное, и что ещё хуже, первые коэффициенты сильно больше последних по модулю. Сильно — это примерно на 1-2 порядка. Причины две — во-первых, в реальных данных низкочастотные гармоники всегда больше, во-вторых, в нашем случае высокочастотные гармоники приглушены нами же — исходный вектор длины K => разница между двумя соседними значениями в нём по модулю не больше A/K, так как разница между двумя соседними значениями в профиле последовательности либо 0, либо 1, либо −1. Следовательно, максимум i-го коэффициента примерно (K+1-i)*A/K. Второй: при линейном поиске и сравнении мы же не сравниваем вектора целиком. Мы их сравниваем последовательно от 1-ой координаты к K-ой, то есть в порядке убывания абсолютных значений коэффициентов, а значит, в среднем и разности. То есть большая часть неподходящих нам векторов отсекается вообще по 1-ой координате. Мало — по второй, ещё меньше — по третьей, и т. п. В реале получается, что по 8-16-ым не отсекается вообще почти ничего, а по где-то 7-и из них — совсем ничего. В то же время для полной проверки ''подходящего'' вектора нужно сделать точно K сравнений. То есть, 90 % неподходящих векторов дают часть сложности, сравнимую с полной проверкой оставшихся 10 %. Соответственно, даже если мы изобретём индекс, который позволит нам сразу отсечь почти все 90 % — мы убьём только примерно половину сложности. Потому что индекс никогда не выдаст сразу точно 10 %, а выдаст, скажем, 15 %, которые ещё нужно проверить и ещё 5 % отсечь. Соответственно и максимальное ускорение с помощью любого индекса зависит в основном от процента подходящих векторов и размерности. Чем больше потенциально подходит — тем хуже, чем больше размерность — тем хуже.

* Разбить последовательность на слова и проиндексировать их с учётом возможных сдвигов.* Использовать вместо классических базисов целочисленный вэйвлетоподобный базис, порождаемый из замены двух чисел на их сумму и разность.* Но использовать сами вэйвлеты, то есть когда получается разности не вполне раскладываются повторно, не совсем верно.