#algorithm
#алгоритм
Вопрос:
Предположим, у нас есть двоичный массив A размера n , и все 1 находятся посередине, а все 0 — с обеих сторон 00011000 . Мы не знаем количество единиц, и массив может быть не симметричным, и нам гарантировано, что по крайней мере 1 позиция i, что A[i] = 1 и по крайней мере одна позиция j:j<i, A[j]=0 и по крайней мере одна позиция k:k>i, A[k]=0 .
Каким может быть эффективный алгоритм, возможно, со сложностью poly(log n) , чтобы найти индекс разделения между 0 и 1, т. Е. Индекс i такой, что (A[i]=1,A[i-1]=0) или (A[i]=1, A[i 1]=0) ? Есть ли у нас название для этой проблемы?
Комментарии:
1. Вопрос неясен. Каковы ограничения? Является ли массив симметричным? Есть ли хотя бы один 0 и один 1? Что вы подразумеваете под индексом разделения?
Ответ №1:
Тривиальное решение является оптимальным
Вы, вероятно, заметили, что вы можете решить эту проблему за линейное время, просто выполнив итерацию по массиву.
Теперь рассмотрим ситуацию, в которой в массиве есть только один 1 . Все, что мы можем сделать, чтобы найти это 1 , это проверять каждую позицию, пока не найдем ее. Пока 1 не найден, мы найдем только 0 те, которые не дают нам никакой информации о местонахождении 1 . Конечно, нам не нужно проверять первый или последний элемент массива, поскольку они гарантированно будут 0 , но это существенно не помогает.
Вы можете добиться большего успеха на квантовом компьютере
На квантовом компьютере вы можете использовать алгоритм Гровера для поиска 1 в O(sqrt n) , после чего вы можете найти любой из индексов разделения с помощью простого двоичного поиска, в общей сложности O(sqrt(n) log(n)) = O(sqrt n) .