排序矩阵搜索主定理分析

Question

所以问题是要找出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.如果值较大，则搜索矩阵的右上右下左下的值

Answer 1

我不知道这是否正确，但我使用的是主定理的第二种情况

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

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

当k= 0时，f(R) =θ(R^(log4(3)=θ(R^(log4(3))* logk(R))成立，因此时间复杂度为：

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

Answer 2

递归关系

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

这是显而易见的，因为在每一步中，你都会丢弃1/4的搜索空间，并3次查看1/4的剩余空间。

根据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))

这就是我所在的地方，stuck..Can，我们减少RHS？忘了我的高中数学。

尽管如此，我仍然会被纠正。