Какова будет временная сложность разделения массива на две части и нахождения минимального элемента в целом?
Это O (n) или O (log n)?
известен предел разделов?
@user16320675 user16320675 нет, сэр, пределы неизвестны. Я просто хочу знать, какова временная сложность, когда мы делим массив на два отсортированных раздела, а затем находим минимальный элемент.
Сложность разделения (несортированного) массива на 2 отсортированных раздела составляет O(NlogN)
.
Если у вас есть два отсортированных раздела, O(1)
нужно найти наименьший элемент в любом из них... и, следовательно, в обоих разделах.
(Наименьший элемент отсортированного раздела — первый.)
Если массив A уже разбит на две отсортированные части P1 и P2, где P1 распределен по индексам A 0 <= i < k
, а P2 по индексам k <= i < n
с произвольным индексом k из диапазона 0 <= k < n
.
Тогда вы знаете, что наименьший элемент обоих разделов является их первым. Доступ к первому элементу обоих разделов имеет временную сложность O(1)
, а сравнение двух наименьших полученных значений снова имеет временную сложность O(1)
.
Итак, общая сложность поиска минимального значения в массиве, разделенном на два отсортированных раздела, составляет O(1)
.
Вместо этого, если данный массив A должен быть отсортирован в двух отсортированных разделах (потому что это требование), а затем вам нужно найти его минимальный элемент. Затем вам нужно разделить массив на два раздела с произвольным индексом k, отсортировать два раздела с помощью наиболее эффективного алгоритма сортировки, который имеет сложность O(n log n)
, а затем применить ту же логику, описанную выше, для поиска минимального элемента.
Для любого заданного значения k, где k 0 <= k < n
, нам пришлось бы применить алгоритм сортировки дважды (в обоих разделах). Однако, поскольку аддитивное свойство вычисления сложности утверждает, что сложение двух сложностей одного порядка по-прежнему равно той же сложности, то, например, для k = n/2
мы получим следующее: O(n/2 log n/2) + O(n/2 log n/2)
по-прежнему производит O(n log n)
. В общем, O(k log k) + O((n-k) log (n-k))
с 0 <= k < n
и n => ∞
, что все равно даст нам O(n log n)
из-за свойства постоянных множителей. Наконец, нам нужно учесть эту сложность постоянной сложности O(1)
нахождения минимального элемента среди двух разделов, что все равно даст нам O(n log n)
.
В заключение, общая сложность для разделения массива A на два раздела P1 и P2 и нахождения минимального элемента в целом составляет O(n log n)
.
Можете ли вы привести пример, который поможет нам помочь вам здесь?