Постановка задачи.
Дана матрица N на M с произвольными числами и тем свойством, что значения чисел в каждой строке не убывают, а в каждом столбце не возрастают
Задача определить, есть ли в матрице заданный элемент A.
Для начала, если вы не слышали об этой задаче прежде, попробуйте найти для нее решение за O(N+M).
Далее решение Алисы:
Задачу можно решить за O(log S * log S), где S - это максимум из ширины и высоты матрицы, следующим образом: возьмем нашу матрицу, без потери общности допустим, что ширина больше высоты. Возьмем средний столбец, и бинарным поиском будем искать А. Мы можем прийти к одному из трех случаев (не учитывая случай, что мы нашли А - тогда все очевидно):
1. Все элементы в столбце больше А, то есть бинарный поиск сошелся на самом нижнем элементе и не нашел А. Так как значения в строках возрастают, очевидно, что правее этого стобца все числа также больше А, а значит дальше имеет смысл рассматривать только левую половину матрицы.
2. Все элементы в столбце меньше А. Аналогично, только отбрасываем левую половину и повторяем решения для правой половины.
3. В столбце есть как элементы больше, так и элементы меньше. Бинарный поиск в конце концов остановился на какой-то ячейке, значение которой меньше А, такой, что прямо над ней находится ячейка, значение в которой больше чем А. Тут очевидно, что все элементы левее и ниже этой ячейки меньше А, а все элементы правее и выше - больше, то есть мы можем отбросить все, что левее и ниже или правее и выше. Можно понять, что при этом будет отброшена не менее чем половина всех элементов (можно нарисовать, чтобы понять почему - грубо говоря, в каждой строке будет отброшена либо левая половина, либо правая - так как в каждой строке будет отброшена хотя бы половина, то и в целом по матрице будет отброшена хотя бы половина).
Таким образом, не зависимо от обстоятельств, хотя бы половина элементов матрицы будет отброшена, а значит нам надо выполнить не более log(S) шагов, на каждом из которых мы выполним один бинарный поиск, сложность которого O(log(S)), таким образом общая сложность решения - O(log S * log S).
Опровержение Боба:
Построим квадратную матрицу, в которой все элементы выше не главной диагонали равны +oo, все элементы ниже не главной диагонали равны -oo, а все элементы на этой самой не главной диагонали равны случайным числам. Эта матрица удовлетворяет условию задачи. Совершенно очевидно, что если бы в такой матрице можно было найти заданный элемент быстрее, чем за линейное время, то для произвольного массива из N элементов можно было бы найти заданный элемент быстрее, чем за линейное время, а это не правда. Значит решения быстрее чем за линейное время быть не может.
Так кто же ошибается, Алиса или Боб?
Дана матрица N на M с произвольными числами и тем свойством, что значения чисел в каждой строке не убывают, а в каждом столбце не возрастают
Задача определить, есть ли в матрице заданный элемент A.
Для начала, если вы не слышали об этой задаче прежде, попробуйте найти для нее решение за O(N+M).
Далее решение Алисы:
Задачу можно решить за O(log S * log S), где S - это максимум из ширины и высоты матрицы, следующим образом: возьмем нашу матрицу, без потери общности допустим, что ширина больше высоты. Возьмем средний столбец, и бинарным поиском будем искать А. Мы можем прийти к одному из трех случаев (не учитывая случай, что мы нашли А - тогда все очевидно):
1. Все элементы в столбце больше А, то есть бинарный поиск сошелся на самом нижнем элементе и не нашел А. Так как значения в строках возрастают, очевидно, что правее этого стобца все числа также больше А, а значит дальше имеет смысл рассматривать только левую половину матрицы.
2. Все элементы в столбце меньше А. Аналогично, только отбрасываем левую половину и повторяем решения для правой половины.
3. В столбце есть как элементы больше, так и элементы меньше. Бинарный поиск в конце концов остановился на какой-то ячейке, значение которой меньше А, такой, что прямо над ней находится ячейка, значение в которой больше чем А. Тут очевидно, что все элементы левее и ниже этой ячейки меньше А, а все элементы правее и выше - больше, то есть мы можем отбросить все, что левее и ниже или правее и выше. Можно понять, что при этом будет отброшена не менее чем половина всех элементов (можно нарисовать, чтобы понять почему - грубо говоря, в каждой строке будет отброшена либо левая половина, либо правая - так как в каждой строке будет отброшена хотя бы половина, то и в целом по матрице будет отброшена хотя бы половина).
Таким образом, не зависимо от обстоятельств, хотя бы половина элементов матрицы будет отброшена, а значит нам надо выполнить не более log(S) шагов, на каждом из которых мы выполним один бинарный поиск, сложность которого O(log(S)), таким образом общая сложность решения - O(log S * log S).
Опровержение Боба:
Построим квадратную матрицу, в которой все элементы выше не главной диагонали равны +oo, все элементы ниже не главной диагонали равны -oo, а все элементы на этой самой не главной диагонали равны случайным числам. Эта матрица удовлетворяет условию задачи. Совершенно очевидно, что если бы в такой матрице можно было найти заданный элемент быстрее, чем за линейное время, то для произвольного массива из N элементов можно было бы найти заданный элемент быстрее, чем за линейное время, а это не правда. Значит решения быстрее чем за линейное время быть не может.
Так кто же ошибается, Алиса или Боб?
Поднял тему с дна форума, потому что очень интересно стало решение задачи. Если в сообщении выше и есть ответ, то прошу прощения, ибо я его слегка не понял, и прошу разъяснить, а если ответа все же не было, или ответ, который выше, неправильный, то, может быть, кто-нибудь ответит? Спасибо :)
Заполним матрицу одинаковыми числами, например A[i][j]==100 для всех i,j.Очевидно, что матрица удовлетворяет условию. Начнем искать по заданному алгоритму, очевидно, что мы просмотрим log(n) столбцов в каждом их которых n элементов. Значит, сложность n*log(n). UPD. Искать будем что-то !=100. UPD2. Если мы выкинем часть, которая правее и выше и левее и ниже, то у нас останутся ещё 2 части, о которых ничего наверняка сказать нельзя, то есть их надо проверять отдельно. Ещё можно заметить, что диагональные элементы никогда не исключаются из просмотра.
Решение Алисы в случае одномерного массива можно было бы представить так:
Понятно, что такое решение не работает.
Вообще говоря, Алиса могла бы и выкидывать тот столбец, в котором она проводила двоичный поиск.
Если я не туплю, то Алиса и вправду ошибается.После каждого шага мы получаем две задачи, которые нужно решить независимо. То есть:
1) На первом шане нам нужно сделать log(S) действий
2) На втором — 2*log(s/2) = 2*log(s)-1 действий.
3) На третьем — 4*log(s/4) = 4*log(s)-2 действий и так далее.
Всего шагов будет log(s). И того выйдет что суммарно нам надо сделать (1+2+4+...+log(s))log(s) — (1+2+..+log(s)-1) = (2^(log(s)-1))*log(s)-log(s)*(log(s)-1)/2 = S*log(s)/2-log(s)*(log(s)-1)/2 действий. То есть сложность получается O(Slog(S)), Алиса не права.