Какова временная сложность деления матрицы пополам при выполнении над ней операции O (n ^ 2)?
Предположим, у вас есть две квадратные матрицы m1 и m2 размера n X n. Алгоритм итеративно выполняет над ними операцию O(n^2), уменьшая вдвое матрицы на каждой итерации. Что-то вроде псевдокода ниже:
while m1.width > 0:
u = m1 & m2 # pairwise logical and operation (O(n^2))
m1 = halve(m1)
m2 = halve(m2)
Поскольку цикл повторяется log(n) раз, O(n^2.log(n)) является верхней границей временной сложности алгоритма. Я ищу более жесткую верхнюю границу. Любые идеи?
Я ожидаю более жесткой верхней границы, основанной на предположении, что размер матриц, для которых оценивается O(n^2), логарифмически уменьшается.
Ответы 2
Неясно, что такое «половина», но если предположить, что это число делит пополам n (а не количество элементов в матрице), этот расчет показывает O (n ^ 2): n ^ 2 + (n/2) ^ 2 + (n/4) ^ 2 + ... = n ^ 2 * (1 + 1/4 + 1/16 + ...) = 4n ^ 2/3.
Если это вдвое уменьшает количество элементов в матрице, то у вас есть этот расчет (который также дает O (n ^ 2)): n ^ 2 + n ^ 2/2 + n ^ 2/4 + ... = n ^ 2 (1 + 1/2 + 1/4 + 1/8 + ...) = 2n ^ 2.
Обычный трюк, используемый здесь при вычислении сложности алгоритмов деления пополам, состоит в том, чтобы довести сумму до бесконечности, а не останавливаться, когда n/2 ^ k достигает 1. Это дает точную верхнюю границу.
При таком цикле часто лучше складывать работу, проделанную за каждую итерацию, а не умножать работу, проделанную за одну итерацию, на количество итераций. В конце концов, работа, выполняемая за итерацию, меняется.
Опуская на мгновение нотацию O, ваша первая итерация выполняет примерно n ^ 2 работы, как для вычисления И, так и для уменьшения размера матрицы вдвое. Теперь, сколько работы делает вторая итерация? Что ж, поскольку ваши матрицы в два раза меньше, чем раньше, в каждом измерении, работа, проделанная для их И, примерно равна (n / 2) ^ 2 = n ^ 2 / 4. Когда вы снова делите матрицы вдвое, следующее И выполняет (n / 4)^2 = n^2 / 16 работ. В более общем случае, в k-й раз, когда вы проходите цикл, ваша операция AND будет выполнять n^2/4^k работы.
Суммируя это во всех итерациях цикла, мы получаем, что общая проделанная работа равна
n^2 / 4^0 + n^2 / 4^1 + n^2 / 4^2 + …
= n^2 · (1 / 4^0 + 1/4^1 + 1/4^2 + …)
Этот последний бит представляет собой сумму геометрического ряда, и в сумме он составляет 4/3. Итак, это дает нам, что общая проделанная работа составляет мои 4n ^ 2 / 3, что составляет O (n ^ 2).
Другой способ увидеть это: хотя ваш код написан итеративно, вы можете представить, что думаете о нем как о рекурсивном алгоритме, который работает O (n ^ 2), а затем снова запускается на входе размером n / 2. Это дает повторение
T(n) = T(n / 2) + O(n^2).
Затем основная теорема говорит вам, что (с a = 1, b = 2, d = 2 и log_b a < d) решение равно O (n ^ 2).