Что такое «асимптотически точная оценка времени работы алгоритма»?

Привет всем грызущим гранит. Разбираю Кормена "Алгоритмы. Построение и анализ". Для более глубокого понимания проглядываю материалы из других источников - некоторые моменты изложены примитивнее и быстрее оседают. Наткнулся на статью algolist.manual.ru/misc/o_n.php . Сразу же зацепился за определение точной оценки Θ():
Оценка Θ() существует только тогда, когда O() и Ω() совпадают и равна им.
Итак, O() - асимптотическая оценка алгоритма на худших входных данных, Ω() - на лучших входных данных, Θ() - сокращенная запись одинаковых O() и Ω().
два сомнительных момента. Несмотря на то, что звучали они как очевидно ошибочные, я понял что запутался и не усвоил понятие точной оценки ( Θ() ).
Кормен уклончиво сообщает, что иногда дать точную оценку (оценить среднее время работы алгоритма) проблематично из-за того, что не всегда очевидно какие входные данные для данной задачи будут усредненными. Он же говорит, что точная оценка представляет из себя множество функций, заключенных между константными отклонениями от оцениваемой функции. Но насколько я понял, границы эти не есть верхняя O() и нижняя оценки Ω(). Это просто константы, ограничивающие множество Θ(). Оценка Θ() может быть использована для получения оценок O() и Ω() и наоборот, при этом справедливо следующее - Ω() принадлежит Θ() принадлежит O(). Вот здесь, очевидно, я плыву потому что вики вещает следующее:
Θ() дает одновременно верхнюю и нижнюю оценки роста функции
Известно, что например для сортировки qsort средняя оценка для случайного распределения входных данных (она же лучшая, для полностью сбаллансированного варианта) равна Θ(nlogn), тогда как верхняя оценка (для специально подобранных неоптимальных данных) равна O(n^2).
Также известно, что сортировка вставками в лучшем случае дает Ω(n) (для предварительно отсортированного набора), тогда как средняя и худшая оценки равны Θ(n^2) и O(n^2).
Кормен, если опять же я правильно понимаю, говорит что на практике имея верхнюю и нижнюю оценки получают точную оценку, делая более строгие/мягкие предположения - это академически.
Правильно ли будет сказать, что реально асимптотически точная оценка алгоритма дается в первую очередь на основании особенностей работы конкретного алгоритма для усредненных входных данных (понимая под усредненными данными случайно распределенный массив данных), а в сложных случаях - отталкиваясь от оценок сверху O() и снизу Ω()? Являются ли процитированные утверджения из статьи ошибочными?
  • Вопрос задан
  • 8584 просмотра
Пригласить эксперта
Ответы на вопрос 1
@throughtheether
human after all
Мое авторитетное мнение дилетанта таково.
Во-первых, имеет смысл ознакомиться с первоисточником по данной теме, а именно со статьей Дональда Кнута. В ней на стр.19 дается удобное, на взгляд автора, определение отношений Θ,O,Ω. Эти отношения первоначально задаются как отношения значений неких двух функций. Оценка временной и пространственной сложности - это приложения. Целью введения такой нотации было упростить вычисление количества операций, требуемых для выполнения алгоритма, без потери качественных характеристик, а также отвязаться от возможных зависимостей от архитектуры, компилятора и т.д. Грубо говоря, если алгоритм обсчитывает 1000 единиц входных данных час, то эта нотация помогает быстро оценить, как долго будут обсчитываться, например, 2000 единиц. Естественно, что эта нотация "огрубляет" информацию о значениях функции, в этом ее предназначение.

Что такое «асимптотически точная оценка времени работы алгоритма»?
Если речь идет о Θ-нотации, то это функция (или множество функций), растущая так же быстро, как и время работы алгоритма с увеличением длины входных данных.

Оценка Θ() существует только тогда, когда O() и Ω() совпадают и равна им.
Это положение мне представляется частично верным. Если f(n)=O(g(n)) и f(n)=Ω(g(n)), то f(n)=Θ(g(n)), где g(n) - некая функция, например, вида nlogn. Другое дело, что если f(n)=O(n), то также верно, что f(n)=O(n^2), то есть, несмотря на то, что у функции есть Θ-оценка, ее O- и Ω-оценки могут не совпадать.

Итак, O() - асимптотическая оценка алгоритма на худших входных данных, Ω() - на лучших входных данных
Если определить "лучшие"/"худшие" данные как требующие минимального/максимального времени среди наборов входных данных такой же длины, то это утверждения мне также представляется частично корректным. Количество операций, которое выполняет алгоритм в худшем, среднем и лучшем случаях - это функции от длины входных данных. Каждую из этих функций можно оценить при помощи каждой из трех (Ω,Θ,O) нотаций.

Мне представляется разумным такое восприятие оценок:
f(n)=O(g(n)) - функция f(n) растет не быстрее функции g(n)
f(n)=Ω(g(n)) - функция f(n) растет не медленнее функции g(n)
f(n)=Θ(g(n)) - функция f(n) растет так же быстро, как и функция g(n)
Попробуйте нарисовать график некоей возрастающей функции в логарифмическом масштабе по оси ординат, и представить, где расположены значения функций, корректно оценивающих исходную при помощи Ω,O,Θ нотаций, пользуясь определениями из статьи Кнута и отметив на графике константы C и n0.


Известно, что например для сортировки qsort средняя оценка для случайного распределения входных данных (она же лучшая, для полностью сбаллансированного варианта) равна Θ(nlogn),
С моей точки зрения, корректно также будет сказать, что средняя оценка также равна O(nlogn) или Ω(n).

тогда как верхняя оценка (для специально подобранных неоптимальных данных) равна O(n^2).
а также равна Θ(n^2).

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

Пользуясь случаем, рекомендую курс на coursera от Tim Roughgarden. Релевантные видео есть на youtube.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы