Основы объектно-ориентированного программирования на языке C# book | Page 32

2 Oснови алгоритмiзацiı̈
Сумнiвiв, який з алгоритмiв ефективнiший, здається, не виникає.
Для алгоритмiв, подiбних до щойно розглянутого (n крокiв для
обробки n вхiдних значень), кiлькiсть крокiв є функцiєю вiд кiлькостi
елементiв, що обробляються, – g(n). Не для кожного алгоритму таку
функцiю можна легко обчислити.
Для оцiнки швидкостi зростання дослiджуваноı̈ функцiı̈ порiвняємо
ı̈ı̈ з функцiєю, дiя якоı̈ вже добре вiдома. При дослiдженнi поведiнки
функцiй g(n) натурального n розглядатимемо такi функцiı̈ g(n), що
зростають не швидше f (n), тобто iснує така пара додатних значень
M i n 0 , що |g(n)| ≤ M |f (n)| для n ≥ n 0 . Таку залежнiсть позна-
чають у математицi символом O: g(n) = O(f (n)). Iнодi символ O
використовують у рiвняннях злiва i справа вiд знаку рiвностi, на-
приклад f (n, O(r 1 (n)), ..., O(r k (n))) = g(n, O(s 1 (n)), ..., O(s m (n))). Та-
кi рiвняння слiд розумiти таким чином: для кожного кортежу фун-
кцiй (p 1 , ..., p k ), такого, що p 1 (n) = O(r 1 (n)), ..., p k (n) = O(r k (n)) iснує
кортеж функцiй (q 1 , ..., q m ), такий, що q 1 (n) = O(s 1 (n)), ..., q m (n) =
O(s m (n)) i для всiх n має мiсце f (n, p 1 (n), ..., p k (n)) = g(n, q 1 (n), ..., q m (n)).
Слiд зауважити, що у рiвняннях, що включають символ O знак рiв-
ностi має сенс однобiчноı̈ рiвностi: з O(g(n)) = O(f (n)) в загальному
випадку не випливає, що O(f (n)) = O(g(n)).
Укажемо кiлька важливих властивостей O–оцiнювання:
1. f (n) = O(f (n));
2. cO(f (n)) = O(f (n)), де c – деяка константа;
3. O(f (n)) + O(f (n)) = O(f (n));
4. O(O(f (n))) = O(f (n));
5. O(f (n))O(g(n)) = O(f (n)g(n));
6. O(cf ) = O(f ), де c – деяка константа;
7. O(f + g) дорiвнює домiнантi O(f ) i O(g).
Можна сказати, що ефективнiсть алгоритму безпосереднього пiдсу-
мовування n елементiв вiдповiдає лiнiйнiй складностi, оскiльки його
швидкодiя, тобто кiлькiсть крокiв, згiдно iз властивiстю 1 становить
O(n).
Розглянемо таку задачу: для набору з n попарно нерiвних вiдрiзкiв
пiдрахувати кiлькiсть усiх трiйок, з яких можна отримати невиро-
дженi трикутники.
32