Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[8]

заключать, что fi(n) = /2(га)!

Определение Q(g(n)) предполагает, что функции /(га) и д(п) асимптотически неотрицательны, т.е. неотрицательны для достаточно больших значений га. Заметим, что если функции fug строго положительны, то можно исключить по из определения (изменив константы с\ и с2 так, чтобы для малых га неравенство также выполнялось).

Если /(га) = Q(g(n)), то говорят, что д(п) является асимптотически точной оценкой для /(га). На самом деле это отношение симметрично: если /(га) = Q(g(n)), то д(п) = ©(/(га)).

Вернёмся к примеру из главы 1 и проверим, что (1/2)га2 - Зга = ©(га2). Согласно определению, надо указать положительные константы С\,С2 и число по так, чтобы неравенства

cira2 -га2 - Зга с2га2

выполнялись для всех га гао- Разделим на га2:

13

2га

Видно, что выполнения второго неравенства достаточно положить с2 = 1/2. Первое будет выполнено, если (например) щ = 7 и с\ = 1/14.

Другой пример использования формального определения: покажем, что 6га3 ф 0(га2). В самом деле, пусть найдутся такие с2 и по, что 6га3 с2га2 для всех га uq. Но тогда га с2/6 для всех га гао - что явно не так.

Отыскивая асимптотически точную оценку для суммы, мы можем отбрасывать члены меньшего порядка, которые при больших га становятся малыми по сравнению с основным слагаемым. Заметим также, что коэффициент при старшем члене роли не играет (он может повлиять только на выбор констант с\ и с2). Например, рассмотрим квадратичную функцию /(га) = an2 + Ьп + с, где а,Ь,с - некоторые константы и а > 0. Отбрасывая члены младших порядков и коэффициент при старшем члене, находим, что /(га) = 0(га2). Чтобы убедиться в этом формально, можно положить с\ = а/4, с2 = 7а/4 и гао = 2 • тах((6/а), -\/с/а) (проверьте, что требования действительно выполнены). Вообще, для любого полинома р(п) степени d с положительным старшим коэффициентом имеем р(га) = 0(rad) (задача 2-1).

Упомянем важный частный случай использования 0-обозначений: 0(1) обозначает ограниченную функцию, отделённую от нуля некоторый положительной константой при достаточно больших значениях аргумента. (Из контекста обычно ясно, что именно считается аргументом функции.)


О- и -обозначения

Запись /(га) = Q(g(n)) включает в себя две оценки: верхнюю и нижнюю. Их можно разделить. Говорят, что /(га) = 0(д(п)), если найдётся такая константа с > 0 и такое число по, что 0 f(n) сд(п) для всех га по Говорят, что /(га) = Q(g(n)), если найдется такая константа с > 0 и такое число щ, что 0 сд(п) f(n) для всех га по. Эти записи читаются так: «эф от эн есть о большое от же от эн», «эф от эн есть омега большая от же от эн».

По-прежнему мы предполагаем, что функции fug неотрицательны для достаточно больших значений аргумента. Легко видеть (упр. 2.1-5), что выполнены следующие свойства:

Теорема 2.1. Для любых двух функций /(га) и д(п) свойство /(га) = Q(g(n)) выполнено тогда и только тогда, когда /(га) = 0(g(n)) и f(n) = Q(g(n)).

Для любых двух функций свойства /(га) = 0(g(n)) и g(n) = £}(f(n)) равносильны.

Как мы видели, an2 + Ъп + с = 0(га2) (при положительных а). Поэтому an2 + Ъп + с = 0(п2). Другой пример: при а > 0 можно написать an А-Ь = 0(п2) (положим с = а + 6 и щ = 1). Заметим, что в этом случае an Л-Ь ф Q(n2 и an -\-Ъ ф 0(га2).

Асимптотические обозначения (в, О и S7) часто употребляются внутри формул. Например, в главе 1 мы получили рекуррентное соотношение

Т(п) = 2Г(га/2) + 6(га)

для времени работы сортировки слиянием. Здесь О(га) обозначает некоторую функцию, про которую нам важно знать лишь, что она не меньше с\п и не больше сп для некоторых положительных с\ и С2 и для всех достаточно больших п.

Часто асимптотические обозначения употребляются не вполне формально, хотя их подразумеваемый смысл обычно ясен из контекста. Например, мы можем написать выражение

п

8 = 1

имея в виду сумму h(l) + h(2) + ... + h(n), где h(i) - некоторая функция, для которой h(i) = O(i). Легко видеть, что сама эта сумма как функция от п есть 0(п2).

Типичный пример использования асимптотических обозначений - цепочка равенств наподобие 2га2 + Зга + 1 = 2га2 + О(га) = 0(га2). Второе из этих равенств (2га2 + О(га) = 0(га2)) понимается при этом так: какова бы ни была функция h(n) = О(га) в левой части, сумма 2га2 + h(n) есть 0(га2).


о- и а>обозначения

Запись /(га) = 0(д(п)) означает, что с ростом га отношение f(n)/g(n) остаётся ограниченным. Если к тому же

lim М = 0,(2.1)

га-»схэ д(п)

то мы пишем /(га) = о(д(п)) (читается «эф от эн есть о малое от же от эн»). Формально говоря, /(га) = о(д(п)), если для всякого положительного е > 0 найдётся такое гао, что 0 f(n) £д(п) при всех га по. (Тем самым запись /(га) = о(д(п)) предполагает, что /(га) и д(п) неотрицательны для достаточно больших га.) Пример: 2га = о(га2), но 2га2 ф о(га2).

Аналогичным образом вводится -обозначение: говорят, что /(га) есть uj(g(n)) («эф от эн есть омега малая от же от эн»), если для любого положительного с существует такое гао, что 0 сд(п) f(n) при всех га гао- Другими словами, /(га) = uj(g(n)) означает, что д(п) = о(/(га)).

Пример: га2/2 = oj(n), но га2/2 ф uj(n2).

Сравнение функций

Введённые нами определения обладают некоторыми свойствами транзитивности, рефлексивности и симметричности: Транзитивность:

= е(5(п))

и

(га)

= Q(h(n)) влечёт /(га)

= в(ВД)

= 0(5(п))

и

(га)

= 0{h(n)) влечёт /(га)

1 =0(ВД)

=

и д\

(га)

= Q(h(n)) влечёт /(га)

= Q(h(n)),

= о(</(та))

и #(

га)

= o(h(n)) влечёт /(га) :

= o(h(n)),

= ш(</(та))

и #(

га)

= uj(h(n)) влечёт /(га)

= bj(h(n)).

Рефлексивность:

/(га) = в(Дга)), /(га) = О(Дга)), /(га) = Щ/(п)).

Симметричность:

/(га) = Q(g(n)) если и только если д(га) = в(/(га)).

Обращение:

/(га) = 0(д(п)) если и только если д(п) = i7(/(ra)), /(га) = о(д(п)) если и только если д(п) = uj(f(n)).

Можно провести такую параллель: отношения между функциями fug подобны отношениям между числами а и Ь:

= 0(5(п))

г-~>

а Ь

= Щд{п))

а Ь

= ®{д{п))

а = b

= о(д(п))

а < Ь

= ш(д(п))

г-~>

а > Ь



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]