Временная сложность деления массива пополам

Какова будет временная сложность разделения массива на две части и нахождения минимального элемента в целом?

Это O (n) или O (log n)?

Можете ли вы привести пример, который поможет нам помочь вам здесь?

R.A. Lucas 17.05.2022 09:06

известен предел разделов?

user16320675 17.05.2022 09:13

@user16320675 user16320675 нет, сэр, пределы неизвестны. Я просто хочу знать, какова временная сложность, когда мы делим массив на два отсортированных раздела, а затем находим минимальный элемент.

Amateurz7 17.05.2022 09:21
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
2
3
55
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Сложность разделения (несортированного) массива на 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).

Другие вопросы по теме