С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 5
Текст из файла (страница 5)
Для сложности алгоритма пробных делений было быpошибкой утверждать,что его сложность по числу делеpний есть Θ( n). Но оценка O( n), разумеется, верна и, более того,является точной в смысле следующего определения.Определение .. Если имеет место оценка f (n) = O(g(n)), то онаназывается точной, коль скоро существует неограниченно возрастающая последовательность неотрицательных целых чисел {nk } такая,что для ϕ (k) = f (nk ), ψ(k) = g(nk ) имеет место ϕ (k) = Ω(ψ(k)).Для упомянутых ϕ (k) и ψ(k) в силу этого определения и семантики символа Θ выполнено ϕ (k) = Θ(ψ(k)).При рассмотрении алгоритмапробных делений для доказательpства точности оценки O( n) можно взять nk равным k-му простомучислу, k = 1, 2, ...Понятие точности оценки вида f (n) = O(g(n)) можно определитьтакже с помощью знакомого из математического анализа символа o;напомним, что u(n) = o(v(n)) при n → ∞, коль скоро u(n) = α(n)v(n)и lim α(n) = 0.n→∞Предложение ..
Пусть f (n) = O(g(n)). Эта оценка являетсяточной, если и только если неверно, что f (n) = o(g(n)).Доказательство. Пусть оценка является точной, и {nk } — возрастающая последовательность, о которой говорится в определении .. Тогда существует положительная константа c такая, что| f (nk ) | ¾ c| g(nk ) |, k = 1, 2, ..., и соотношение f (n) = o(g(n)) места неимеет. Обратно, если неверно, что f (n) = o(g(n)), то по определениюсимвола o существуют ǫ > 0 и возрастающая последовательность {nk }натуральных чисел такие, что | f (nk ) | ¾ ǫ| g(nk ) |, k = 1, 2, ... Если при§ . Асимптотические оценки (формализм)этом выполнена оценка f (n) = O(g(n)), то эта оценка точна в соответствии с определением ..Для рассматриваемой сложности алгоритма пробных делений неверна,pскажем, оценка O(log n), потому что для этой сложностиоценpка O( n) является точной и в то же время log n = o( n).Нелишним будет заметить, что сложность алгоритма пробных делений допускает оценки O(n), O(n5 ), O(n log n) и т.
д., хотя,разумеетpся, эти оценки являются более грубыми в сравнении с O( n). Еще разподчеркнем, что оценка f (n) = O(g(n)) есть асимптотическая верхняяоценка, равно как оценка f (n) = Ω(g(n)) — асимптотическая нижняя .Как, например, из l < 5 и m < 100 нельзя вывести, что l < m, так и изf (n) = O(n2 ), g(n) = O(n3 ) нельзя вывести, что хотя бы для достаточнобольших n выполняется f (n) < g(n).
Оценка вида TA (n) = O(g(n)) (илиS A (n) = O(g(n))) подходит для того, чтобы «похвалить» алгоритм A,т. е. охарактеризовать его сложность как достаточно низкую (речьидет лишь об оценках вида O(g(n)), а не о более тонких оценках,включающих символ O и имеющих вид, подобный (.)), но не длятого, чтобы «раскритиковать» его — для таких целей скорее подойдет оценка вида TA (n) = Ω(h(n)). Зная, например, что сложность почислу обменов для сортировки выбором есть O(n), а для сортировкипростыми вставками — Ω(n2 ), мы обоснованно заключаем, что длядостаточно больших n первая сложность меньше второй.Оценки вида TA (n) = Θ(g(n)), соединяющие в себе оценки TA (n) == O(g(n)) и TA (n) = Ω(g(n)), в соответствующих ситуациях подходяти для характеризации сложности как сравнительно низкой, и, наоборот, как сравнительно высокой .При всем этом, иногда можно услышать сообщения о новых алгоритмах, сопровождаемые рассуждениями в духе следующего (подразумевается, что n — размер входа): «Лучший из известных ранееалгоритмов решения этой задачи требует O(n3 ) операций, а предВ книге [] отмечено, что положение с символом O схоже с тем, которое возникнет, если кто-нибудь «вместо слов „меньше чем“ начнет писать = M, например, так:3 = M(5).
На вопрос: „Что значит M(5)?“ — он должен ответить: „Нечто, что меньше, чем 5“. Таким образом, он быстро привыкает читать M как „нечто, что меньше,чем“, приближаясь к тем самым словам, которые употребляем мы, вводя соотношениеf (s) = O(ϕ (s))».Θ- и Ω-нотации вошли в литературу по вычислительной сложности алгоритмовс появлением статьи Д. Кнута [], в которой автор, в частности, пишет о бессмысленности нижних оценок вида O( f (n)) и о невозможности использования оценок такогорода как оценок сложности при сравнении алгоритмов.
В [] отмечается также, чтоΩ-нотация использовалась ранее в работах Э. Ч. Титчмарша, известного математикапервой половины XX века. Глава . Сложности алгоритмов как функции числовых аргументовлагаемый нами алгоритм — лишь O(n). Таким образом, достигнутоулучшение на два порядка по числу операций». Но информация, содержащаяся в первой из этих двух фраз, не дает достаточных оснований для сделанного заключения. Более того, на основе этой информации вообще нельзя сказать, какой из двух алгоритмов — известныйранее или новый — требует меньше операций при больших n, ведьречь идет лишь об оценках сверху, и возможно, что первая из нихможет быть улучшена.Если про оценку O(g(n)) известно, что она точная, то это расширяет возможности ее использования. Допустим, что нам известеналгоритм распознавания простоты числа n, имеющий мультипликативную сложность O(logd n) при некотором d > 0.
Тогда мультипликативная сложность этого алгоритма для бесконечного множества значений n (но, может быть, не для всех n) будет меньше, чем мультипликативная сложность алгоритма пробных делений, и для этоговывода достаточно того, что сложность алгоритма пробных деленийpдопускает точную оценку O( n).В тех случаях, когда рассматриваются два или более параметровразмера входа, мы можем по-прежнему использовать асимптотические оценки вида Θ(g(n1 , n2 )), где под знаком Θ расположена функция двух переменных n1 , n2 , причем n1 , n2 → ∞; определение Θ легкомодифицируется на случай двух и большего числа переменных:f (n1 , n2 ) = Θ(g(n1 , n2 )) ⇐⇒⇐⇒ ∃c1 ,c2 ,N >0 ∀n1 ,n2 >N c1 | g(n1 , n2 ) | ¶ | f (n1 , n2 ) | ¶ c2 | g(n1 , n2 ) |.(.)То же самое с Ω, O и o.
При этом, если имеет место оценка f (n1 , n2 ) == O(g(n1 , n2 )), то мы назовем ее точной, коль скоро неверно, чтоf (n1 , n2 ) = o(g(n1 , n2 )).Утверждение, что f (n) и g(n) асимптотически эквивалентны, записываемое как f (n) ∼ g(n), означает, как известно, что f (n) = g(n) ++ o(g(n)) = g(n)(1 + o(1)). Утверждение, что f (n) ∼ g(n), является,очевидно, более сильным, чем утверждение, что f (n) = Θ(g(n)).
Заметим кстати, что из формул (.) следует1TeI2 (n) ∼ n2(.)2 1= n2 (1 + o(1))), но не(например, TeI1 (n) = n2 + O(n) = n2 1 + Onнаоборот. Из (.) следует только, чтоTeI1 (n) ∼ n2 ,TeI1 (n) = n2 + o(n2 ),1TeI2 (n) = n2 + o(n2 ),2§ . Асимптотические оценки (два примера)при этом из v(n) = o(n2 ) не следует, что v(n) = O(n), что доказываетсяпримером v(n) = n3/2 .Слова « f (n) имеет асимптотику g(n)» означают, что f (n) ∼ g(n);например, TeI1 (n) имеет асимптотику n2 , а TeI2 (n) имеет асимптотику1 2n .2Сложности многих алгоритмов трудно или невозможно представить элементарного вида функциями от размера входа. Помимо этого, точное значение сложности алгоритма для каждого конкретного значения размера входа часто не представляет особого интереса,актуальным же является исследование роста сложности при возрастании размера входа.
Поэтому асимптотическое оценивание широкоиспользуется в теории сложности.§ . Асимптотические оценки (два примера)Если мы изначально имеем эскизное описание алгоритма, не содержащее мелких деталей, но полностью отражающее его идею, то ужеэтого эскиза может быть достаточно для получения некоторой информативной асимптотической оценки сложности; проработка деталейалгоритма будет влиять на скрытые за символами O, Ω, Θ значенияконстант.Пример .. Займемся задачей построения выпуклой оболочки конечного множества M точек координатной плоскости, т.
е. выпуклогомногоугольника H, содержащего все множество M (рис. ). Множест-а)б)Рис. . a) Конечное множество M точек плоскости; б) выпуклая оболочкамножества M .во M задается массивом координат принадлежащих ему точек; требуется построить массив координат вершин многоугольника H приобходе этого многоугольника, начиная с какой-нибудь его вершины, Глава . Сложности алгоритмов как функции числовых аргументовпротив часовой стрелки (считаем, что это направление совпадаетс направлением обхода точек (0, 0), (1, 0), (0, 1), (0, 0)).Пусть n — число элементов множества M, будем считать это число размером входа.
Алгоритм, основанный на переборе всех подмножеств множества M с проверкой для каждого из них, является ли оно множеством вершин искомого многоугольника H, имееточень высокую сложность Ω(2n ). Обсудим идею значительно болееэкономного алгоритма Р. Л. Грэхема (этот алгоритм мы обозначимбуквой G).Можно довольно быстро найти среди точек множества M такую,которая обязательно будет одной из вершин многоугольника H: достаточно выбрать в M точку P с наименьшей ординатой, а если такихточек несколько, то из этих нескольких взять ту, которая имеет наименьшую абсциссу. Дополнительно найдем точку O, которая принадлежит многоугольнику H, но не совпадает ни с одной из точек множества M: возьмем для этого какие-нибудь две точки из M и найдемсередину соединяющего их отрезка (если впоследствии вдруг окажется, что эта точка принадлежит M, то можно будет удалить ее из M,так как она заведомо не является вершиной H).Используя какую-нибудь сортировку с помощью сравнений, всеточки множества M можно упорядочить по возрастанию углов междуотрезком OP и отрезками, соединяющими O с точками множества M,при этом мы считаем, что величина каждого угла принадлежит полуинтервалу [0, 2π).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
