анализ основной теоремы поиска по сортированной матрице

Таким образом, проблема состоит в том, чтобы найти, находится ли x в одном из элементов отсортированной матрицы, возрастающей по строке и по столбцу.

пример :

1 2 3

4 5 6

7 8 9

Мне интересно найти временную сложность решения этой проблемы по принципу «разделяй и властвуй». Я погуглил, но нашел только для решения O (m + n), а также из этого Поиск в отсортированной 2D-матрице. но он говорит (комментарий к ответу), что «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. если значение больше, ищите значение в верхнем правом, нижнем правом, нижнем левом углу матрицы


algorithm matrix time-complexity master-theorem divide-and-conquer
person bysreg    schedule 12.02.2013    source источник
comment
Что такое top_row, top_col и т. д. Можете ли вы дать псевдокод вместо фактического кода.. спасибо   -  person smk    schedule 12.02.2013
comment
@SajitKunnumkal, я отредактировал свой вопрос. чтобы уточнить мое решение. top_row — это индекс самой верхней строки матрицы, которую нужно проверить на предмет значения x, и то же самое касается top_col и т. д.   -  person bysreg    schedule 12.02.2013
comment
f(n) — стоимость слияния частей. не должно ли T(R) быть T(n)?   -  person thang    schedule 12.02.2013
comment
@thang под T(R) означает R = mxn (m — максимальная строка, а n — максимальный столбец), хотя я изменил f(n) на f(R)   -  person bysreg    schedule 12.02.2013

Ответы (2)


arrow_upward
1
arrow_downward

Рекуррентное соотношение

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

ясно, потому что на каждом шаге вы отбрасываете 1/4 пространства поиска и просматриваете остальную часть 1/4 пространства 3 раза.

Согласно вики, 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? Забыл школьную математику.

Я стою, чтобы быть исправленным, хотя.

person smk    schedule 12.02.2013
comment
и какова должна быть временная сложность приведенного выше решения с использованием основной теоремы? потому что это главный вопрос. Спасибо, в любом случае - person bysreg; 12.02.2013
comment
действительно ли вы отбрасываете 1/4 пространства поиска и просматриваете остальные 3/4? Я думал, что это больше похоже на то, что вы просматриваете 1/4 пространства поиска 3 раза. - person thang; 12.02.2013
comment
возможно, но не обязательно... по уравнению этого не скажешь. - person thang; 12.02.2013
comment
@SajitKunnumkal, может быть, вы можете подробнее объяснить, как вы получаете O (log (4R / 3))? - person bysreg; 12.02.2013
comment
это правильно. Я сделал ошибку @bysreg. Исправление моего ответа - person smk; 12.02.2013
comment
@thang, не могли бы вы подтвердить, правильно ли мое последнее уравнение и есть ли способ уменьшить RHS? - person smk; 12.02.2013
comment
хорошо, одна вещь, которая поможет, состоит в том, чтобы предположить, что n = 4^p для некоторого целого числа p для простоты. затем обратите внимание, что вы можете развернуть только p раз, прежде чем получите T (1). поэтому T (4 ^ p) = 3 T (4 ^ (p-1)) + f (n) = ... = 3 ^ p T (1) + pf (n) и подставьте p = log (n) / журнал (4). а теперь в общем случае заметим, что для любого n всегда найдутся p1 и p2 такие, что 4^p1 ‹ n ‹ 4^p2. - person thang; 13.02.2013
comment
@thang, можешь ответить на вопрос в новом посте? потому что я действительно не понимаю твоего объяснения - person bysreg; 18.02.2013

arrow_upward
0
arrow_downward

Я не знаю, правильно ли это, но я использую случай 2 главной теоремы.

Т(R) = 3T(R/4) + тета(1)

f (R) = тета (1) = тета (R) = тета (R ^ (log4 (3)))

f (R) = theta (R ^ (log4 (3))) = theta (R ^ (log4 (3)) * logk (R)) верно с k = 0, поэтому временная сложность:

T (R) = тета (R ^ (log4 (3)) * log (R)) = тета (R ^ 0,8 * log (R))

person bysreg    schedule 12.02.2013
comment
Почему дело 2? Мы можем использовать случай 2, если c = Theta (n ^ (0,8)) - Можем ли мы это доказать? - person smk; 12.02.2013
comment
@smk требование случая 2: f(R) = theta((R^c) * (log(R))^k), где c = logb a истинно для некоторой константы k›=0. ну, как видно из второй строки моего поста (f(R) = theta(1) = theta(R) = theta(R^(log4(3)))) theta(R^log4(3)) == тета ((R ^ c) * (log (R)) ^ k) с k = 0 - person bysreg; 18.02.2013