Время выполнения алгоритма для генерации матрицы Хадамара

Question

Я пытаюсь разработать алгоритм для создания матрицы Адамара, используя технику разделения и покорения. Для этого я решил использовать четыре рекурсивных вызова для генерации каждого члена матрицы, а затем продолжить с рекурсивными вызовами на каждом шаге для матрицы Адамара с одним значением меньше. Например, H (3) разделяется на 4 H (2) слагаемые с одним отрицательным и так далее до H (0). При разработке рекуррентного соотношения я закончил с

C(n) = 4C(n-1) + 1. 

Однако следует разделять и властвовать включать разделение входа вместо уменьшения на 1? Концептуально, однако, я бы подумал, что разделение матрицы на подмножества меньших матриц будет квалифицироваться как разделение и покорение. В любом случае, у меня закончилось время работы 4^n. Является ли это точной для алгоритма, который я разработал?

Answer 1

Это точно. При интерпретации n окончательной матрицей является 2^n -by- 2^n, с 4^n элементами. Рекуррентное с участием m, число элементов, будет

T(m) = 4T(m/4) + 1, 

с раствором, который O(m).