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

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

Это 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
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
Четыре эффективных способа центрирования блочных элементов в CSS
Четыре эффективных способа центрирования блочных элементов в CSS
У каждого из нас бывали случаи, когда нам нужно отцентрировать блочный элемент, но мы не знаем, как это сделать. Даже если мы реализуем какой-то...
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).

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