Мое авторитетное мнение дилетанта таково.
Во-первых, имеет смысл ознакомиться с первоисточником по данной теме, а именно со
статьей Дональда Кнута. В ней на стр.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.
