Подтвердить что ты не робот

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

Я застрял в двух временных сложностях. Для выполнения двоичного поиска с отсортированным массивом O (logN). Поэтому для поиска несортированного массива мы должны сначала отсортировать его, чтобы он стал O (NlogN). Итак, мы можем выполнить двоичный поиск, который дает сложность как O (N), но я прочитал, что это может быть O (NlogN). Что правильно?

4b9b3361

ОТВЕТЫ

Ответ 1

Двоичный поиск предназначен для списков "Сортировка". Сложность - O (logn).

Двоичный поиск не работает для списков "un-Sorted". Для этих списков просто выполните прямой поиск, начиная с первого элемента; это дает сложность O (n). Если бы вы отсортировали массив с MergeSort или любым другим алгоритмом O (nlogn), тогда сложность была бы O (nlogn).

O (logn) O (n) O (NlogN)

Ответ 2

Ответ на ваш вопрос находится в самом вашем вопросе.

Вы сначала сортируете список. Если вы сортируете свой список, используя быструю сортировку или сортировку слиянием, сложность становится o(n*log n). Часть - 1 проходит.

Вторая часть выполнения двоичного поиска выполняется в "Сортированном списке". Сложность бинарного поиска составляет o(log n). Поэтому в конечном итоге сложность программы остается o(n*log n).

Однако, если вы хотите вычислить медиану массива, вам не нужно сортировать список. Простое применение линейного или последовательного поиска может помочь вам в этом.

Ответ 3

Временная сложность линейного поиска O(n), а бинарный поиск - O(log n) (log base-2). Если у нас есть несортированный массив и мы хотим использовать бинарный поиск для этого, мы должны сначала отсортировать массив. И здесь мы должны потратить время O(n logn), чтобы отсортировать массив, а затем потратить время на поиск элемента.