0

所以问题是找出 x 是否在按行和按列升序的排序矩阵的元素之一中。

例子 ：

1 2 3

4 5 6

7 8 9

我有兴趣找到这个问题的分而治之解决方案的时间复杂度。我用谷歌搜索了它，但我只找到了 O(m+n) 解决方案，并且还从这个Search a sorted 2D matrix中找到了。但他说（对答案发表评论）“T(R) = 3T(R/4)”，为什么 f(R) = 0？

问题是使用主定理的分而治之解决方案的复杂性是什么？在 T(R) = 3T(R/4) + f(R) 中，f(R) 应该是多少？

如果有帮助，这是我的分而治之的解决方案：

bool find_x_in_matrix(int x, int mat[3][3], int top_row, int top_col, int bot_row, int bot_col) {
if(top_row > bot_row || top_col > bot_col)
    return false;

int mid_row = (bot_row + top_row) / 2;
int mid_col = (bot_col + top_col) / 2;

if(mat[mid_row][mid_col] == x)
    return true;
else if(mat[mid_row][mid_col] > x) {
    return find_x_in_matrix(x, mat, top_row, mid_col, mid_row - 1, bot_col) ||
        find_x_in_matrix(x, mat, top_row, top_col, mid_row-1, mid_col-1) || 
        find_x_in_matrix(x, mat, mid_row, top_col, bot_row, mid_col-1);
}else if(mat[mid_row][mid_col] < x) {
    return find_x_in_matrix(x, mat, top_row, mid_col + 1, mid_row, bot_col) || 
        find_x_in_matrix(x, mat, mid_row + 1, top_col, bot_row, mid_col) || 
        find_x_in_matrix(x, mat, mid_row + 1, mid_col + 1, bot_row, bot_col);       
}
}

编辑以澄清解决方案：

算法： 1. 将矩阵的中间元素与搜索值进行比较 2. 如果值等于 m(i,j)，则返回 true 3. 如果值较小，则搜索矩阵的右上角、左上角、左下角的值矩阵 4. 如果值较大，则在矩阵的右上角、右下角、左下角搜索值

4

2 回答 2

1

递归关系

T(R) = 3T(R/4) + c

很清楚，因为在每一步中，您都在丢弃 1/4 的搜索空间并查看剩余的 1/4 空间 3 次。

根据 wiki，f(n) 是在递归调用之外完成的工作的成本，其中包括划分问题的成本和将解决方案合并到子问题的成本。

我认为这只是一个常数。f(n) 可能不为零，但它绝对是一个常数值，并且不依赖于搜索空间。

编辑：

我不确定如何使用主定理，但如果我们展开递归关系，我们会得到

 T(n) = 3^2* T(n/(4^2)) + c(1 + 3)

前进，T(n) = 3^k * T(n/4^k) + c(3^0 + 3^1 ... + 3^(k-1))

这就是我卡住的地方..我们可以减少 RHS 吗？忘记了我的高中数学。

不过，我必须得到纠正。

于 2013-02-12T06:23:45.203 回答
0

我不知道这是否正确，但我正在使用主定理的案例 2

T(R) = 3T(R/4) + theta(1)

f(R) = theta(1) = theta(R) = theta(R^(log4(3)))

f(R) = theta(R^(log4(3))) = theta(R^(log4(3)) * logk(R)) 在 k = 0 时为真，因此时间复杂度为：

T(R) = theta(R^(log4(3)) * log(R)) = theta(R^0.8 * log(R))

于 2013-02-12T08:07:13.400 回答