Что именно представляет собой большая not нотация?

сначала давайте разберемся, что такое big O, big Theta и big Omega. Они все наборы функций.

Big O дает верхний асимптотическая граница, в то время как большая Омега дает нижнюю границу. Большая тета дает обоим.

все это Ө(f(n)) тоже O(f(n)), но не наоборот.
T(n) находится в Ө(f(n)) Если это и в O(f(n)) и Omega(f(n)).
в комплекте терминологии, Ө(f(n)) is элемент пересечение на O(f(n)) и Omega(f(n))

например, наихудший случай сортировки слиянием-это оба O(n*log(n)) и Omega(n*log(n)) - и поэтому тоже Ө(n*log(n)), а также O(n^2) С n^2 асимптотически "больше", чем он. Однако, это неӨ(n^2), так как алгоритм не Omega(n^2).

немного более глубокое математическое объяснение

O(n) является асимптотической верхней границей. Если T(n) и O(f(n)), это означает, что от некоего n0 постоянно C такое, что T(n) <= C * f(n). С другой стороны, большая Омега говорит, что есть константа C2 такое, что T(n) >= C2 * f(n))).

не путай!

не путать с худшим, лучшим и средним анализом случаев: все три (Омега, о, тета) обозначения не связанные с лучшими, худшими и средними случаями анализа алгоритмов. Каждый из них может быть применен к каждому анализу.

мы обычно его используют для анализа сложности алгоритмов (как пример сортировки слиянием выше). Когда мы говорим: "алгоритм-это O(f(n))", на самом деле мы имеем в виду " сложность алгоритмов при худшем¹ анализ случая O(f(n)) "- означает-он масштабирует "аналогичную" (или формально не хуже) функцию f(n).

почему мы заботимся об асимптотической границе алгоритма?

Ну, есть много причин для этого, но я считаю, самое главное они таковы:

1. гораздо труднее определить точно функция сложности, таким образом, мы "идем на компромисс" по нотациям big-O/big-Theta, которые достаточно информативны теоретически.
2. точное количество ОПС также зависит от платформы. Например, если у нас есть вектор (список) из 16 цифр. Сколько это будет стоить? Ответ таков: это зависит. Некоторые процессоры допускают векторные дополнения, в то время как другие нет, поэтому ответ варьируется между разные реализации и разные машины, что является нежелательным свойством. Однако нотация big-O гораздо более постоянна между машинами и реализациями.

чтобы продемонстрировать эту проблему, посмотрите на следующие графики:

понятно, что f(n) = 2*n "хуже", чем f(n) = n. Но отличие не столь радикально, как от другой функции. Мы видим, что f(n)=logn быстро становится намного ниже, чем другие функции и f(n) = n^2 быстро становится намного выше, чем другие.
So-из-за вышеуказанных причин мы "игнорируем" постоянные факторы (2* в примере графиков) и берем только обозначение big-O.

в приведенном выше примере f(n)=n, f(n)=2*n обоих в O(n) и Omega(n) - и таким образом тоже будет в Theta(n).
с другой стороны - f(n)=logn будет O(n) (это "лучше", чем f(n)=n), но не будет Omega(n) - и таким образом тоже не будет в Theta(n).
симметрично, f(n)=n^2 будет Omega(n), но не O(n), а значит-тоже не Theta(n).

---

¹обычно, хотя и не всегда. когда класс анализа (худший, средний и лучший) отсутствует, мы действительно имеем в виду худшем случае.

чтобы ответить на ваш вопрос, необходимо также объяснить асимптотическую нотацию и функции в асимптотической нотации. Если у вас есть терпение, чтобы прочитать все это, все будет очень понятно в конце.

1. Асимптотическая нотация

думать об алгоритмах вы можете использовать 2 основные идеи:

1. определите, сколько времени занимает алгоритм с точки зрения его ввода.
2. фокус на том, как быстро функция растет с размером входного сигнала; ака скорость роста хода время. Пример: предположим, что алгоритм, работающий на входе размера n, принимает 6N^2 + 100n + 300 машинных инструкций. Член 6n^2 становится больше остальных членов, 100 n + 300, как только n становится достаточно большим, в этом случае 20.

мы бы сказали, что время работы этого алгоритма растет как n^2, отбрасывая коэффициент 6 и остальные члены 100n + 300. На самом деле не имеет значения, какие коэффициенты мы используем; пока работает время-этоn^2 + bn + c, для некоторых чисел a > 0, b и c всегда будет значение n, для которого an^2 больше, чем bn + c, и эта разница увеличивается с увеличением n. Отбрасывая постоянные коэффициенты и менее значимые члены, мы используем асимптотическую нотацию.

2. Биг-Тета

вот простая реализация линейного поиска

var doLinearSearch = function(array) {
  for (var guess = 0; guess < array.length; guess++) {
    if (array[guess] === targetValue) { 
        return guess;  // found it!
    }
  }
  return -1;  // didn't find it
};

• каждый из этих вычислений требует постоянного количество времени каждый раз, когда он выполняет. Если цикл for повторяется n раз, то время для всех n итераций равно c1 * n, где c1-сумма времен для вычислений в одной итерации цикла. Этот код имеет немного дополнительных накладных расходов, для настройки for-loop (включая инициализацию guess до 0) и, возможно, возвращает -1 в конце. Назовем время для этих накладных расходов c2, которое также является константой. Таким образом, общее время линейного поиска в худшем случае c1*n+c2.
• постоянный фактор c1 и член низкого порядка c2 не говорят нам о скорости роста времени выполнения. Важно то, что наихудшее время выполнения линейного поиска растет как размер массива n. обозначение, которое мы используем для этого времени выполнения, Θ(n). Это греческая буква "тета", и мы говорим" большая тета n "или просто " тета n".

• когда мы говорим, что определенное время выполнения Θ(n), мы говорим, что как только n становится большим достаточно, что время выполнения составляет не менее k1*n и не более k2 * n для некоторых констант k1 и k2. Вот как думать о Θ(n)

• для малых значений n нам все равно, как время выполнения сравнивается с k1*n или k2 * n. но как только n становится достаточно большим-На или справа от пунктирной линии - время выполнения должно быть зажато между k1*n и k2 * n. пока эти константы k1 и k2 существуют, мы говорим, что время выполнения равно Θ (n).

• когда мы используем большую-not нотацию, мы говорим, что у нас есть асимптотически туго связан на время работы. "Асимптотически", потому что это имеет значение только для больших значений n."крепко связаны" потому что мы прибили время выполнения в пределах постоянного фактора выше и ниже.

3. Функции в асимптотической нотации

• предположим, что алгоритм постоянное количество времени, независимо от размер входного сигнала. Например, если вам дали массив, который уже отсортирован в порядке возрастания, и вам нужно было найти минимальный элемент, это займет постоянное время, так как минимальный элемент должен быть в индексе 0. Поскольку нам нравится использовать функцию n в асимптотической нотации, можно сказать, что этот алгоритм работает в Θ(n^0) времени. Зачем? Потому что n^0 = 1, а время работы алгоритма находится в пределах некоторого постоянного коэффициента 1. На практике мы не пишем Θ (n^0), однако; мы пишем Θ(1)
• вот список функций в асимптотической нотации, с которыми мы часто сталкиваемся при анализе алгоритмов, перечисленных от самого медленного до самого быстрого роста. Этот список не является исчерпывающим; есть много алгоритмов, время работы которых здесь не отображается:
• Θ (1) (он же постоянный поиск)
• Θ (lg n) (aka binary search)
• Θ (n) (он же линейный поиск)
• Θ (n*lg n)
• Θ (n^2)
• Θ(n^2 * lg n)
• Θ (n^3)

• Θ (2^n)

• 1, растет быстрее, чем любая полиномиальная функция n^b, где b-любая константа.

4. Big-O notation

• мы используем большую-not нотацию, чтобы асимптотически связать рост времени выполнения с постоянными факторами выше и ниже. Иногда мы хотим быть связанными только сверху. Было бы удобно иметь форма асимптотической записи, которая означает: "время выполнения растет не более этого, но оно может расти медленнее."Мы используем обозначение" big-O " именно для таких случаев.
• если время выполнения равно O (f (n)), то для достаточно большого n время выполнения не более k*f(n) для некоторой постоянной k. вот как думать о времени выполнения, которое равно O (f (n)):
• если вы вернетесь к определению обозначения big-Θ, вы заметите, что оно очень похоже на обозначение big-O, за исключением того, что большая-not нотация ограничивает бег как сверху, так и снизу, а не только сверху. Если мы говорим, что время выполнения Θ(f(n)) в конкретной ситуации, то это также O(f(n)). Например, мы можем сказать, что, поскольку наихудшее время выполнения двоичного поиска-Θ(lg n), это также O(lg n). Обратное не обязательно верно: как мы видели, мы можем сказать, что двоичный поиск всегда выполняется в O(lg n) время, но не то, что он всегда работает в Θ(lg n) время.
• Предположим, у вас есть 10 долларов в кармане. Вы подходите к своему другу и говорите: "у меня есть деньги в кармане, и я гарантирую, что это не более одного миллиона долларов."Ваше утверждение абсолютно верно, хотя и не очень точным. Один миллион долларов-это верхняя граница на 10 долларов, так же как O(n) - верхняя граница времени выполнения двоичного поиска.
• другие, неточные, верхние границы двоичного поиска будут O(n^2), O(n^3) и O (2^n). Но никто из Θ(N) и Θ(п^2),Θ(П^3), andΘ(2^н​​) было бы правильно описать время выполнения бинарного поиска в любом случае.

5. Большой Ω (Биг-Омега) обозначения

• иногда мы хотим сказать, что алгоритм занимает по крайней мере определенное количество времени, не предоставляя верхнюю границу. Мы используем обозначение big-Ω; это греческая буква " omega."
• если время выполнения Ω (f (n)), то для достаточно большого n время выполнения по крайней мере k*f(n) для некоторой константы k. вот как думать о выполнении время, которое является Ω(f (n)):
• мы говорим, что время выполнения "большой-Ω из f(n)."Мы используем нотацию big-Ω для асимптотических нижних границ, поскольку она ограничивает рост времени выполнения снизу для достаточно больших входных размеров.
• так же, как Θ(f(n)) автоматически подразумевает O(f(n)), он также автоматически подразумевает Ω(f(n)). Таким образом, мы можем сказать, что наихудшим временем выполнения двоичного поиска является Ω(lg n). Мы также можем сделать правильные, но неточные утверждения, используя big-Ω нотация. Например, так же, как если бы у вас действительно был миллион долларов в кармане, вы можете честно сказать: "у меня есть сумма денег в кармане, и это по крайней мере 10 долларов", вы также можете сказать, что наихудшее время выполнения двоичного поиска-Ω(1), потому что это занимает по крайней мере постоянное время.

ссылка: https://www.khanacademy.org

тета (n): функция f(n) принадлежит Theta(g(n)), если существуют положительные константы c1 и c2 такое, что f(n) можно зажать между c1(g(n)) и c2(g(n)). то есть он дает как верхнюю, так и нижнюю границу.

Theta(g (n)) = {f(n): существуют положительные константы c1, c2 и n1 такие, что 0=n1 }

когда мы говорим f(n)=c2(g(n)) или f(n)=c1(g(n)) он представляет собой асимптотически плотную границу.

O (n): это дает только верхнюю границу (может или не может быть жесткой)

O (g (n)) = {f(n): существуют положительные константы c и n1 такие, что 0=n1}

ex: связанный 2*(n^2) = O(n^2) асимптотически плотно, тогда как граница 2*n = O(n^2) не является асимптотически плотным.

o (n): It дает только верхнюю границу (никогда не жесткую границу)

заметная разница между O (n) & o (n) является f (n) меньше, чем cg(n) для всех n>=n1, но не равно, как в O (n).

ex:2*n = o(n^2), а 2*(n^2) != o(n^2)