0

したがって、問題は、x が行ごとおよび列ごとに昇順で並べ替えられた行列の要素の 1 つに含まれているかどうかを調べることです。

例 ：

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 に答える