Здравствуйте!

Я уверен что не понимаю очень ключевую вещь в анализе временной сложности алгоритмов.

Верхняя асимптотическая граница есть подмножеством O(n*n) а нижняя Ω(n).
Получаться что O(n*n) не равно Ω(n).
Следует ли считать что для сортировки вставкой не существует
точной асимптотический границы?
И что это значит?

Надеюсь многие люди найдут полезным узнать ответ на этот вопрос.

Спасибо.

Здравствуйте, garkus, Вы писали:

G>Здравствуйте!

G>Я уверен что не понимаю очень ключевую вещь в анализе временной сложности алгоритмов.

G>Верхняя асимптотическая граница есть подмножеством O(n*n) а нижняя Ω(n).
G>Получаться что O(n*n) не равно Ω(n).

Ну в общем да.:) А иначе нафига нужно было бы иметь две границы?

G>Следует ли считать что для сортировки вставкой не существует
G>точной асимптотический границы?
G>И что это значит?

Это значит, что бывает, что входные данные пришли уже полностью или почти отсортированными.

G>Надеюсь многие люди найдут полезным узнать ответ на этот вопрос.

?

G>>Верхняя асимптотическая граница есть подмножеством O(n*n) а нижняя Ω(n).
G>>Получаться что O(n*n) не равно Ω(n).

N>Ну в общем да. А иначе нафига нужно было бы иметь две границы?

В чем тогда смысл Ө, если есть две границы?

Здравствуйте, garkus, Вы писали:

G>>>Верхняя асимптотическая граница есть подмножеством O(n*n) а нижняя Ω(n).
G>>>Получаться что O(n*n) не равно Ω(n).

N>>Ну в общем да.:) А иначе нафига нужно было бы иметь две границы?

G>В чем тогда смысл Ө, если есть две границы?

Давайте вначале уточним символы. В первом случае была омега, во втором тета. Что именно имеется в виду? Насколько я помню курс, омега означала асимптотический предел снизу. В таком случае, что Вас удивляет, что он вообще измеряется? Представьте себе, например, необходимость получить алгоритм сложности менее O(n). (Например, O(log n).) В таком случае, этой нижней оценки уже достаточно, чтобы понять, что в этом алгоритме не может использоваться сортировка (вообще любая, если нет заранее данных о свойствах данных в последовательности), так как простейшая проверка факта сортированности уже стоит Ω(n). Надеюсь, мысль понятна?

G>>>>Верхняя асимптотическая граница есть подмножеством O(n*n) а нижняя Ω(n).
G>>>>Получаться что O(n*n) не равно Ω(n).

N>>>Ну в общем да. А иначе нафига нужно было бы иметь две границы?

G>>В чем тогда смысл Ө, если есть две границы?

N>Давайте вначале уточним символы. В первом случае была омега, во втором тета. Что именно имеется в виду? Насколько я помню курс, омега означала асимптотический предел снизу. В таком случае, что Вас удивляет, что он вообще измеряется? Представьте себе, например, необходимость получить алгоритм сложности менее O(n). (Например, O(log n).) В таком случае, этой нижней оценки уже достаточно, чтобы понять, что в этом алгоритме не может использоваться сортировка (вообще любая, если нет заранее данных о свойствах данных в последовательности), так как простейшая проверка факта сортированности уже стоит Ω(n). Надеюсь, мысль понятна?

Тогда получается оценка Ө вообще не нужна!

Или же может Ө просто указывает на класс сложности алгоритма, например для алгоритма сложности O(n*n) принадлежит классу сложности Ө(n*n). Правильные ли мои подозрения?

Здравствуйте, garkus, Вы писали:

N>>Давайте вначале уточним символы. В первом случае была омега, во втором тета. Что именно имеется в виду? Насколько я помню курс, омега означала асимптотический предел снизу. В таком случае, что Вас удивляет, что он вообще измеряется? Представьте себе, например, необходимость получить алгоритм сложности менее O(n). (Например, O(log n).) В таком случае, этой нижней оценки уже достаточно, чтобы понять, что в этом алгоритме не может использоваться сортировка (вообще любая, если нет заранее данных о свойствах данных в последовательности), так как простейшая проверка факта сортированности уже стоит Ω(n). Надеюсь, мысль понятна?

G>Тогда получается оценка Ө вообще не нужна!

Моя ваша не понимай. Почему не нужна? Я же описал, зачем она нужна.

G>Или же может Ө просто указывает на класс сложности алгоритма, например для алгоритма сложности O(n*n) принадлежит классу сложности Ө(n*n). Правильные ли мои подозрения?

Не понимаю.

Здравствуйте, netch80, Вы писали:

N>Здравствуйте, garkus, Вы писали:

N>>>Давайте вначале уточним символы. В первом случае была омега, во втором тета. Что именно имеется в виду? Насколько я помню курс, омега означала асимптотический предел снизу. В таком случае, что Вас удивляет, что он вообще измеряется? Представьте себе, например, необходимость получить алгоритм сложности менее O(n). (Например, O(log n).) В таком случае, этой нижней оценки уже достаточно, чтобы понять, что в этом алгоритме не может использоваться сортировка (вообще любая, если нет заранее данных о свойствах данных в последовательности), так как простейшая проверка факта сортированности уже стоит Ω(n). Надеюсь, мысль понятна?

G>>Тогда получается оценка Ө вообще не нужна!

N>Моя ваша не понимай. Почему не нужна? Я же описал, зачем она нужна.

G>>Или же может Ө просто указывает на класс сложности алгоритма, например для алгоритма сложности O(n*n) принадлежит классу сложности Ө(n*n). Правильные ли мои подозрения?

N>Не понимаю.

Если в данном тексте:

"Представьте себе, например, необходимость получить алгоритм сложности менее O(n). (Например, O(log n).) В"

вместо O вы имели ввиду Ө, то все понятно.

Здравствуйте, garkus, Вы писали:

G>Верхняя асимптотическая граница есть подмножеством O(n*n) а нижняя Ω(n).
G>Получаться что O(n*n) не равно Ω(n).
G>Следует ли считать что для сортировки вставкой не существует
G>точной асимптотический границы?
Ага, для произвольных входных данных точной асимптотической оценки не существует.
Однако, если алгоритму на вход подавать лишь отсортированные (в нужном порядке) последовательности, можно сказать, что время его работы составляет Ө(n). Кстати, для алгоритма верны также границы Ω(1) и O(n^125)
Асимптотическая оценка — лишь обозначение количества требуемых ресурсов (времени или памяти) для некоторого множества входных данных.
На одном и том же множестве для худшего случая это будет O, для лучшего — Ω, если оценки совпадут, то появится еще и Ө.
В Кормене все доступно описано.

G>>Верхняя асимптотическая граница есть подмножеством O(n*n) а нижняя Ω(n).
G>>Получаться что O(n*n) не равно Ω(n).
G>>Следует ли считать что для сортировки вставкой не существует
G>>точной асимптотический границы?
_>Ага, для произвольных входных данных точной асимптотической оценки не существует.
_>Однако, если алгоритму на вход подавать лишь отсортированные (в нужном порядке) последовательности, можно сказать, что время его работы составляет Ө(n). Кстати, для алгоритма верны также границы Ω(1) и O(n^125)
_>Асимптотическая оценка — лишь обозначение количества требуемых ресурсов (времени или памяти) для некоторого множества входных данных.
_>На одном и том же множестве для худшего случая это будет O, для лучшего — Ω, если оценки совпадут, то появится еще и Ө.
_>В Кормене все доступно описано.

Спасибо.
Я вкурил