2-D сложность пикового поиска (MIT OCW 6.006)

В видео- чтении для MIT OCW 6.006 в 43:30,

Учитывая матрицу размером с столбцами и строками, алгоритм поиска двумерных пиков, в котором пиковое значение представляет собой любое значение, большее или равное соседним соседям, было описано как:$m \times n$м $A$$m$$n$

Примечание. Если при описании столбцов через возникает путаница , я приношу свои извинения, но именно так это описывает видео-декламация, и я старался соответствовать этому видео. Это очень смутило меня.$n$

1. Выберите средний столбец // Имеет сложностьΘ ( 1 )$n/2$$\Theta(1)$

2. Найти максимальное значение столбца // Имеет сложность потому что в столбце строкΘ ( м ) м$n/2$$\Theta(m)$$m$

3. Проверьте горизонт. соседние строки по максимальному значению, если оно больше, чем пик, было найдено, в противном случае рекурсивно с // Имеет сложностьТ ( н / 2 , м )$T(n/2, m)$$T(n/2,m)$

Затем, чтобы оценить рекурсию, инструктор декламации говорит

$T(1,m) = \Theta(m)$ потому что находит максимальное значение

$$T(n,m) = \Theta(1) + \Theta(m) + T(n/2, m) \tag{E1}$$

Я понимаю следующую часть, в 52:09 в видео, где он говорит рассматривать как константу, поскольку число строк никогда не меняется. Но я не понимаю, как это приводит к следующему продукту:$m$

Я думаю, что, поскольку обрабатывается как константа, он, таким образом, обрабатывается как и исключается из выше. Но мне трудно прыгнуть на . Это потому, что мы сейчас рассматриваем случай с постоянной ?$m$$\Theta(1)$$(E1)$$(E2)$$T(n/2)$$m$

Я думаю, что «вижу» общую идею в том, что операция выполняется, в худшем случае, для числа m строк. Я пытаюсь понять, как описать переход от к кому-то еще, т.е. получить реальное понимание.$\Theta(\log n)$$(E1)$$(E2)$

Насколько я понимаю, требуется (m) времени, чтобы оценить все элементы в данном столбце и определить, какой из этих элементов является глобальным максимумом. Когда приходит Θ ( lg ( n ) ), это то, что в худшем случае алгоритм должен оценить столбцы lg ( n ) в матрице, прежде чем будет найден пик. Общая работа будет тогда Θ ( млн. Гл ( n ) $\Theta$$\Theta (\lg(n))$$\lg(n)$$\Theta(m\lg(n))$

Например, предположим, что ваша матрица имеет 32 столбца и 8 строк.

1. Вы берете средний столбец, скажем, столбец 16. Вы оцениваете его и обнаруживаете, что глобальный пик столбца заменен элементом справа. Вы отбрасываете столбцы 1-16 и сосредотачиваетесь на столбцах 17-32.
2. Найдите средний столбец оставшейся матрицы, который является столбцом 24, и вы оцениваете глобальный пик (это ваша оценка второго столбца). Вы обнаружите, что вам нужно двигаться вправо. Оставьте столбцы 17-24, сфокусируйтесь на 25-32.
3. Найдите середину (столбец 28) - вы оцениваете (третий столбец оценки), и вы обнаружите, что нужно двигаться вправо. Отбросьте столбцы 25 - 28 и сосредоточьтесь на 29 - 32.
4. Оцените колонку 30 (четвертая оценка), найдите, что вам нужно переместиться вправо, отбросьте колонки 29-30.
5. Оцените один из оставшихся столбцов (оценка пятого столбца), и все готово.

$\lg(32)$$\lg(n)$

$O(m)$$m$$T(n,m)$$T(n,m)$

$\begin{eqnarray*} T(n) & = & T \left({n \over 2}\right) + cn \\ T(n) & = & T(1) + cn \left( 1 + {1 \over 2} + {1 \over 4} + {1 \over 8} + \cdots \right) \\ &= & O(n) \end{eqnarray*}$