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

2 Oснови алгоритмiзацiı̈
A B
C
3 4
5
5 12 13
8 15 17
7 24 25
20 21 29
12 35 37
9
40 41
28 45 53
11 60 61
Табл. 2.3: Трiйки Пiфагора
3. next = small
4 Поки next ≤ n виконуват
Початок
5. last = next
6. Поки last < n виконувати
Початок
7. Якщо last ≤ 2 ∗ small i next ≤ 2 ∗ small i last ∗ last = small ∗
small + next ∗ next
8. то
друк(small) друк(next) друк(last)
9. last = last + 1 кiнцеь циклу last
10. next = next + 1 кiнець циклу next
11. small = small + 1 кiнець цику small
12. Кiнцеь
Вихiд: роздрукованi значення small, next, last.
Легко перевiрити, що складнiсть алгоритму становить O(N 3 ).
Проаналiзувавши програму, можна дiйти висновку, що основну оцiн-
ку складностi забезпечують вкладенi цикли. Тому для зменшення
складностi, перш за все, можна спробувати зменшити глибину вкла-
деностi циклiв. Далi слiд розглянути можливiсть скорочення кiлько-
стi операторiв у циклах з найбiльшою глибиною вкладеностi. Oднак
цi рекомендацiı̈ не завжди можна виконати.
38