Может ли кто-нибудь объяснить Big O против Big Omega vs Big Theta?

Возможный дубликат:
Big Theta Notation - что именно представляет собой большая тэта?

Я понимаю это в теории, я думаю, но то, что я испытываю затруднения, - это применение трех.

В школе мы всегда использовали Big O для обозначения сложности алгоритма. Сорт пузыря был, например, O (n ^ 2).

Теперь, прочитав еще одну теорию, я понял, что Big Oh - это не единственная мера, там, по крайней мере, две другие интересные.

Но вот мой вопрос:

Big O - верхняя граница, Big Omega - нижняя граница, а Big Theta - смесь двух. Но что это значит концептуально? Я понимаю, что это означает на графике; Я видел миллион примеров этого. Но что это означает для сложности алгоритма? Как сочетается "верхняя граница" или "нижняя граница" с этим?

Думаю, я просто не получаю его приложение. Я понимаю, что если умножить на некоторую константу c, то, если после некоторого значения n_0 f (x) больше g (x), f (x) считается O (g (x)). Но что это значит практически? Почему мы будем умножать f (x) на некоторое значение c? Черт, я думал, что многозначные нотации Big O не имеют значения.

Ответ 1

Большая нотация O, и ее родственники, большая Theta, большая Омега, маленькая o и небольшая омега - это способы сказать что-то о том, как функция ведет себя в предельной точке (например, при приближении к бесконечности, но также при приближении к 0 и т.д.), не говоря еще ничего о функции. Они обычно используются для описания пробега и времени алгоритмов, но также могут быть замечены в других областях математики в отношении асимптотического поведения.

Полуинтуитивное определение выглядит следующим образом:

Функция g (x) называется O (f (x)), если "из некоторой точки на", g (x) меньше c * f (x), где c - некоторая константа.

Другие определения аналогичны, Theta требует, чтобы g (x) находилась между двумя постоянными кратными f (x), Omega, требующими g (x) > c * f (x), а малые версии требуют, чтобы это верно для всех таких констант.

Но почему интересно сказать, например, что алгоритм имеет время выполнения O (n ^ 2)?

Это интересно в основном потому, что в теоретической информатике нас больше всего интересует, как алгоритмы ведут себя для больших входов. Это верно, потому что на небольших входах время выполнения алгоритма может сильно варьироваться в зависимости от реализации, компиляции, аппаратного обеспечения и других подобных вещей, которые не очень интересны при теоретическом анализе алгоритма.

Темп роста, однако, обычно зависит от характера алгоритма, и для его улучшения вам нужно более глубокое понимание проблемы, которую вы пытаетесь решить. Это так, например, с алгоритмами сортировки, где вы можете получить простой алгоритм (Bubble Sort) для запуска в O (n ^ 2), но чтобы улучшить это до O (n log n), вам нужна действительно новая идея, такие как введенные в Sort Merge или Heap Sort.

С другой стороны, если у вас есть алгоритм, который выполняется ровно через 5 секунд, а другой, который выполняется за 1000 секунд (это разница между длинной зевотой и разрывом запуска для n = 3, например), когда вы доходите до n = 1000000000000, разница в масштабе кажется менее важной. Если у вас есть алгоритм, который принимает O (log n), вам придется ждать log (1000000000000) = 12 секунд, возможно, умножается на некоторую константу, а не почти 317 098 лет, что, независимо от того, насколько велика постоянная является, совершенно другим масштабом.

Надеюсь, это немного упростит ситуацию. Удачи вам в учебе!