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

2.3 Складнiсть задач
Керувальна структура Складнiсть
Простий вираз O(1)
Лiнiйний вираз S 1 ,...S n Домiнанта O(C 1 ), O(C 2 ),
... O(C n ), де C 1 , C 2 , ..., C n –
складностi обчислення ви-
разiв S 1 , S 2 , ..., S n
Якщо <умова> то дiя1 Iнакше дiя2 Домiнанта O(C 1 ), O(C 2 ),
O(C 3 ), де C 1 , C 2 , C 3 – скла-
днiсть обчислень дiй та
умови, вiдповiдно
Цикл iз n повтореннями тiла S 1
O(n ∙ C 1 ), де C 1 – скла-
днiсть обчислення S 1
Табл. 2.2: Складнiсть керувальних структур
3. початок
4. {Простий вираз}
5. кiнець;
Його складнiсть становить O(N 2 ).
Oцiнимо складнiсть алгоритму, що має назву “Трiйки Пiфагора”.
Суть задачi: знайти всi трiйки натуральних чисел (x, y, z), що задо-
вольняють рiвняння x 2 + y 2 = z 2 . Пiфагор знайшов формули, якi в
сучасному формалiзмi можна записати як
x = 2n + 1, y = 2n(n + 1), z = 2n 2 + 2n + 1,
де n – цiле число. Наприклад:
Трикутники iз такими сторонами є прямокутними. Перед аналi-
зом складностi програми, яка знаходить трiйки Пiфагора, зазначимо,
що iснують два способи аналiзу складностi: висхiдний (вiд внутрi-
шнiх керувальних структур до зовнiшнiх) i низхiдний (вiд зовнiшнiх
– до внутрiшнiх). Ми користуватимемося висхiдним. Розглянемо ал-
горитм.
Алгоритм:
Вхiд: n.
1. small = 1
2. Поки small < n виконувати
Початок
37