我必须计算在矩形矩阵中搜索元素的算法的复杂性。它使用分而治之的方法。对于方阵,我的时间函数变为 a*T(n/b)+O(n^2)。但对于矩形矩阵,如果它必须分为 4 个子矩阵,我不知道如何表示除法。会是 a*T(m*n/4) + O(n) 吗?
最佳答案
您没有描述您的算法,因此无法准确回答问题。但我会尝试假设算法如下:
- 如果
m = 1
或n = 1
,则在O(m * n)
时间内处理矩阵。 - Else (
m > 1
和n > 1
) 将矩阵划分为四个大小不大于[m/2]x[n/2 ]
,其中[y]
是不小于y
的最小整数。 - 使用每个矩阵调用算法。然后“合并”的结果是
O(m * n)
时间。
在这种情况下,时间复杂度的递归方程为
- T(1, n) = O(n)
- T(m, 1) = O(m)
- T(m, n) = 4 * T([m/2], [n/2]) + O(m * n)
让我们来解决这个问题
T(m, n) = O(m * n) +
4 * O([m / 2] * [n / 2]) +
4 ^ 2 * O([m / 4] * [n / 4]) +
... +
4 ^ L * O([m / 2 ^ L] * [n / 2 ^ L]), where L = [log(min(m, n))]
T(m, n) = O(m * n + ... + 4 ^ L * [m / 2 ^ L] * [n / 2 ^ L]) =
= O(m * n + ... + 2 ^ L * [m / 2 ^ L] * 2 ^ L * [n / 2 ^ L] =
= O(m * n + ... + m * n (L times)) =
= O(L * m * n) = O(m * n * [log(min(m, n))])
所以你的问题的答案是
T(m, n) = O(m * n * [log(min(m, n))]),其中 log
代表二进制对数,[y]
代表ceil
函数。
关于c - 矩形矩阵复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22123020/