Обозначение Big O Для доступа к среднему элементу в связанном списке и бинарного поиска?

Question

Статья в http://leepoint.net/notes-java/algorithms/big-oh/bigoh.html говорит, что обозначение Big O Для доступа к среднему элементу в связанном списке - O (N). Не должно быть O (N / 2). Предположим, у нас есть 100 элементов в связанном списке.получить доступ к 50-му элементу, который должен пройти справа от первого до 50-го элемента.Таким образом, число операций будет около 50.

Еще одна большая нотация, определенная для бинарного поиска, - это log (N).Предположим, у нас есть 1000 элементов.Согласно журналу (N) нам потребуется операция, близкая к 3. Теперь давайте вычислим ее вручную, ниже будет шаблон

500-й элемент, 250-й, 125,63,32,16,8,4,2, так что операция около 9, что намного больше, чем 3.

Есть что-то, что я здесь пропускаю?

Answer 1

Чего вам не хватает, так это того, что любые большие кратные значения не имеют значения для Big O. Поэтому мы имеем O (N) = O (N / 2).

Что касается лог-части вопроса, то на самом деле это log ₂ (N), а не log ₁₀ (N), поэтому в этом случае log (1000) на самом деле равно 9 ( при округлении вниз). Также, как и прежде, O (log ₂ (N)) = O (log ₁₀ (N)), поскольку эти два являются постоянными кратными друг другу. В частности, log ₂ (N) = log ₁₀ (N) / log ₁₀ (2)

Последнее, что следует учесть, это то, что, если несколько функций добавляются вместе, функция более низкой степени не имеет значения для Big O. Это потому, что функции более высокой степени растут быстрее, чем функции более низкой степени. Таким образом, мы находим такие вещи, как O (N ³ + N) = O (N ³ ) и O (e ^N + N ² + 1) = O (e ^N ).

Итак, нужно учитывать две вещи: кратность отбрасывания и функцию сброса низкой степени.

Answer 2

O ( n ) означает ", пропорциональный до n , для всех больших n ". ¹

Так что это не должно быть равно n .

Редактировать:

Мое объяснение выше было немного неясным относительно того, что-то вO ( n ) также находится в O (n ² ).Это равно - мое использование слова «пропорциональный» было плохим, и, как другие пытались упомянуть (и, как я изначально неправильно понимал), «сходиться» было бы лучшим термином. ²

_{1: Это на самом деле означает "пропорционально n , когда n велико в худшем случае-case сценарий", но книги обычно рассматривают" средний "случай, который более точно представлен как f(n) ~ n, где f - ваша функция.}

_{2:Для более технических людей: это должно быть очевидно, но я не намереваюсь быть математически строгим.Math.SE может быть лучшим выбором для того, чтобы задать этот вопрос, если вы ищете формальные доказательства (с коэффициентами, ограничениями и прочее).}

Answer 3

Обозначение Big O является общим выражением эффективности алгоритма.Вы не должны рассматривать его как точное уравнение того, насколько быстрым будет алгоритм или сколько памяти ему потребуется, а скорее рассматривать его как приближение.Постоянные множители функции игнорируются, поэтому, например, вы можете просмотреть свой пример как O 1/2 (N) или O k (N), отбросив k , который даетты O (N).

Answer 4

На веб-странице, на которую вы ссылались:

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