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

2 Oснови алгоритмiзацiı̈
Часова складнiсть Oпис програм
O(1) Бiльшiсть операцiй у програмi викону-
ється або один раз, або не бiльш нiж фi-
ксовану кiлькiсть разiв. Будь-який ал-
горитм, що завжди вимагає (незалежно
вiд обсягу даних) одного й того самого
часу, має константну складнiсть.
O(N ) Час роботи програми обмежений лiнiй-
ною функцiєю вiд N. Властиво алгори-
тмам, якi виконують над кожним еле-
ментом вхiдних даних фiксовану кiль-
кiсть операцiй.
O(N 2 ), O(N 3 ), O(N k ) Полiномiальна складнiсть. O(N 2 ) – ква-
дратична складнiсть, O(N 3 ) – кубiчна
складнiсть. Час роботи програми обме-
жений полiномiальною функцiєю.
O(log(N )) Час роботи програми логарифмiчний.
Зустрiчається зазвичай у програмах,
якi дiлять велику задачу на маленькi й
розв’язують одну з них.
O(N log(N )) Такий час роботи мають алгоритми,
якi дiлять велику задачу на малень-
кi, а потiм, розв’язавши ı̈х, сполучають
розв’язки.
O(2 N ) Експоненцiальна складнiсть. Такi алго-
ритми найчастiше виникають унаслiдок
пiдходу, що має назву “метод грубоı̈ си-
ли”.
Табл. 2.1: Часова складнiсть
Якщо один цикл вкладено в iншiй та обидва мають однакову кiль-
кiсть повторень, то вся конструкцiя характеризується квадратичною
складнiстю.
Розглянемо алгоритм.
Алгоритм:
1. Для i = 1 до N виконувати
2. Для j = 1 до N виконувати
36