Итак, это общий вопрос для интервью.Уже есть тема, которую я прочитал, но она мертва, и ответ так и не был принят.Кроме того, мои интересы лежат в несколько более ограниченной форме вопроса с парой практических применений.
Учитывая двумерный массив такой, что:
- Элементы уникальны.
- Элементы сортируются вдоль оси x и оси y.
- Ни одна из сортировок не имеет преимущественного значения, поэтому ни одна из них не является вторичным параметром сортировки.
- В результатедиагональ также отсортирована.
- Все виды можно рассматривать как движущиеся в одном направлении.То есть все они восходящие или все убывающие.
- Технически, я думаю, если у вас есть компаратор> / = / <, любой общий порядок должен работать. </li>
- Элементы представляют собой числовые типы с одноцикловым компаратором.
- Таким образом, операции с памятью являются доминирующим фактором в анализе больших значений.
Как найти элемент?Имеет значение только анализ наихудшего случая.
Решения, которые мне известны:
Разнообразные подходы:
O (nlog (n)), когда вы подходите к каждой строке отдельно.
O(nlog (n)) с сильной лучшей и средней производительностью.
Тот, который является O (n + m):
Начните с неэкстремального угла, который, как мы предположим, будет справа внизу.
Пусть целью будет J. Cur Pos - M.
Если M больше, чем J, двигаться влево.
Если M меньше, чем J, двигаться вверх.
Если вы не можете сделать ни того, ни другого, все готово, а J отсутствует.
Если Mравно J, все готово.
Первоначально найден в другом месте, последний раз украден из здесь .
И я полагаю, что видел один с O (n + m) в худшем случае, но оптимальным случаем почти O (log (n)).
Что мне интересно:
Прямо сейчас я с удовлетворением доказал, что наивная атака с разделами всегда переходит к nlog (n).Атаки с разделением в целом, как представляется, имеют оптимальный наихудший случай O (n + m), и большинство из них не заканчиваются рано в случаях отсутствия.В результате мне также стало интересно, не может ли интерполяционный зонд быть лучше, чем бинарный зонд, и поэтому мне пришло в голову, что можно подумать об этом как о проблеме пересечения множеств со слабым взаимодействием между множествами.Мой разум сразу обратился к пересечению Баэса-Йейтс , но у меня не было времени подготовить адаптацию этого подхода.Однако, учитывая мои подозрения, что оптимальность O (N + M) наихудшего случая доказуема, я подумал, что я просто хочу пойти дальше и спросить здесь, чтобы посмотреть, сможет ли кто-нибудь собрать противоположный аргумент или собрать рекуррентное отношениедля интерполяционного поиска.