Алгоритмы параллельных вычислений и программирование. Бурова И.Г - 26 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

Глава 2. О НЕКОТОРЫХ МЕТОДАХ
ЛИНЕЙНОЙ АЛГЕБРЫ В КОНЦЕПЦИИ
НЕОГРАНИЧЕННОГО ПАРАЛЛЕЛИЗМА
§ 1. Предварительные соглашения
В конце предыдущей главы для оценки эффективности алго-
ритмов пришлось использовать сравнение бесконечно больших ве-
личин. Поскольку это потребуется делать и в дальнейшем, остано-
вимся на понятиях бесконечно больших функций одинакового по-
рядка и эквивалентных бесконечно больших (читатели, знакомые с
этими понятиями, могут пропустить данный параграф).
Рассмотрим положительные функции α(t) и β(t) вещественной
переменной t. Будем считать их бесконечно большими величинами
при t → +∞, а именно, такими, что
lim
t→+∞
α(t) = lim
t→+∞
β(t) = +∞.
Определение 1. Если существуют не зависящие от t кон-
станты t
0
, c
1
и c
2
со свойством
0 < c
1
≤
β(t)
α(t)
≤ c
2
∀t > t
0
,
то говорят, что функции α(t) и β(t) имеют одинаковый порядок
при t → +∞ и пишут α(t)≈β(t).
Определение 2. Если для рассматриваемых функций α(t) и
β(t) выполнено соотношение
lim
t→+∞
α(t)
β(t)
= 1 ,
то α(t) и β(t) называются эквивалентными при t → +∞; при
этом пишут α(t) ∼ β(t).
Очевидно, что эквивалентные функции имеют один порядок.
Если α(t) ≈ β(t) и β(t) = t, то будем писать α(t) = O(t); вообще,
бесконечно большую величину, имеющую порядок величины t при
t → +∞ будем обозначать O(t).
Пример. При a > 0, b > 0, a 6= 1, b 6= 1, t > 0 функции
α(t)
def
=
log
a
t и β(t)
def
=
log
b
t имеют одинаковый порядок при t → +∞,
27

Страницы