Учитывая массив с максимальной кучей неизвестного размера, найдите размер кучи
Мне дан массив размером n, в первых x элементах которого находится максимальная куча (x неизвестен). После этих элементов x каждый элемент имеет значение бесконечности. Моя задача — найти x во временной сложности log(x). Например, если n=2^100 и x окажется равным 30, то мне нужно выполнить 5 операций, а не 100.
До сих пор единственный метод, о котором я думал, заключался в том, чтобы идти вниз по куче (либо только к левым сыновьям, либо к правым сыновьям), пока я не выйду за пределы или не достигну узла, значение следующего дочернего элемента которого равно бесконечности, После этого я буду идти линейно от текущего узла, пока не найду x.
Однако выполненная мной линейная прогрессия имеет временную сложность O(x), и поэтому этот метод дает O(x).
Возможно, я недостаточно тщательно искал, но я еще не видел решений этой проблемы в Интернете. Любая помощь могла бы быть полезна.
Используйте экспоненциально увеличивающийся индекс, соответствующий опусканию левой части кучи, пока значения не бесконечны/свойство кучи сохраняется. Затем используйте нижнюю/верхнюю границу последней строки (теперь вы знаете размер)?
Ответы 1
Продолжайте удваивать проверяемый индекс, пока не дойдете до первой бесконечности. Скажем, это происходит по индексу 2^k.
То есть проверяйте индексы в следующем порядке: 0, 1, 2, 4, 8, 16, 32, ..., 2^(k-1), 2^k. Мы останавливаемся на 2^k, потому что arr[2^k] == бесконечность.
Затем мы выполняем двоичный поиск между 2^(k-1) и 2^k, чтобы найти индекс x.
Это имеет сложность O (log x).
Поправьте меня, если я ошибаюсь, но я не думаю, что двоичный поиск между 2^(k-1) и 2^k приведет к сложности O(log x). Может быть случай, когда в 2^(k-1) и 2^k существует только один элемент x, а все остальные равны бесконечности. В этом случае (представляя, что весь массив представляет собой двоичное дерево) мы практически выполняем двоичный поиск по количеству элементов, зависящему от n, что приведет к временной сложности O (log n).
@razml считайте себя исправленным. 2^(k-1) < x < 2^k так k есть O(log(x)).
Огромное спасибо! потребовалось некоторое время, чтобы понять, что бинарный поиск зависит от x, а не от n, но это определенно так!
Нет, у вас не может быть массива длиной 2^100. Большинство людей понятия не имеют, насколько велики такие числа, как 2^100. Современные компьютеры выполняют операции в диапазоне наносекунд. Давайте будем щедрыми и предположим, что вы каким-то образом приобрели компьютер с пикосекундным тактовым циклом. Если бы вы могли выделять и инициализировать один элемент в пикосекунду, то на 2^100 элементов ушло бы
2^100 / 1E12 / 3600 / 24 / 365.25лет. Разделите это на 14E9, предполагаемый возраст Вселенной, и вы завершите распределение примерно в 2,87 раза больше текущего возраста Вселенной, а затем сможете начать поиск.