Сортировка массива Big o notation

Question

У меня просто есть простой вопрос: почему большая нотация O отсортированного массива O (log N)? Это будет отсортированный массив.

Answer 1

Big O обозначение обычно имеет смысл в контексте алгоритма. Какую операцию вы рассматриваете, когда говорите, что обозначение Big O равно O (log n).

Если вы имеете в виду поиск, то это O (log n), потому что вы можете использовать двоичный поиск. Что по существу означает, что вы смотрите на средний элемент вашего массива, и если он больше, чем тот элемент, который вы ищете, вы затем просматриваете большую половину (таким же образом) и наоборот (если вы еще не нашел ваш элемент, конечно). Вы можете прочитать более подробное описание на wikipedia.

На каждом шаге поиска (глядя на средний элемент) вы сокращаете размер массива, который вы должны искать пополам, так как теперь вы можете узнать, на какой стороне среднего элемента должен находиться ваш элемент поиска. Конечно, это работает только с отсортированными массивами. Для не отсортированных массивов единственным алгоритмом поиска, который вы можете использовать, является линейный поиск, где вы просматриваете каждый элемент массива, который будет принимать средние n/2 проверки.

В целом, Big O описывает характеристики времени выполнения алгоритмов, поэтому вы не можете просто спросить, что такое Big O сортированного массива, это должна быть некоторая операция над массивом. Тем не менее, вы можете рассматривать Big O в терминах пространства (памяти), взятого с помощью некоторой структуры данных. В этом случае отсортированный массив по-прежнему занимает O (n) пространство для хранения N элементов.

Answer 2

Вопрос несколько подделка. Сложность не относится к массиву, но фактически к алгоритму, который сортирует массив (я предполагаю, что вы имеете в виду сложность выполнения, а не память).

Так что в зависимости от используемого алгоритма X в O (X) для сортировки массива может сильно отличаться.

Проверьте эти данные для стартера по сложности в целом и в сортировке массивов специальных случаев.

Introduction to algorithm complexity

Sorting Arrays: Algorithms and Efficiency

Wikipedia: Computational complexity theory