2.2 Складнiсть алгоритмiв
конання такого кроку визначено деяким набором простих , без циклiв , команд мови програмування , або йдеться про ускладнений крок , для якого вiдповiдний аналiз уже проводився i результати вiдомi . Тепер перейдемо до головного питання , яке можна задати будьякому програмiсту : припинить його програма своє виконання або ж працюватиме до нескiнченностi ? За теоремою , доведеною Тьюрiнгом у 30 – тi рр . XX ст ., не iснує алгоритму , що дає вiдповiдь на це питання для довiльноï програми , тобто проблема зупинки алгоритмiчно нерозв ’ язна . Проте у багатьох практичних випадках достатньо легко довести iснування алгоритмiв , якi розв ’ язують поставлену задачу . Тому нас цiкавить не просто iснування алгоритмiв для нашоï задачi , а й ïх ефективнiсть . Причому з усiх складових ефективностi ми звертатимемо особливу увагу на час ( швидкодiю ) роботи алгоритму . Справедливою , хоч i з деякими обмовками , є така формула :
загальний час роботи = кiлькiсть операцiй алгоритму * час на 1 операцiю .
Полiпшення обох членiв у правiй частинi формули здiйснюється незалежно . Грубо кажучи , програми вiдповiдають за перший спiвмножник , а процесори – за другий . Розглянемо деякi приклади .
Алгоритм обмiну значень двох змiнних цiлого типу – a i b – реалiзується в загальному випадку за три кроки , незалежно вiд того , до якого типу простих даних вiн застосовується : temp = a a = b b = temp Якщо застосуємо для обмiну значеннями алгоритм , що використовує арифметичнi операцiï , то дiстанемо таку послiдовнiсть дiй : a = a + b b = a − b a = a − b
Знайти суму натуральних чисел вiд 1 до заданого n . Якщо скористатися вiдомою формулою для суми арифметичноï прогресiï , то для обчислення також знадобляться лише три кроки : додавання , множення й дiлення . Якщо ж реалiзувати обчислювальний процес як циклiчний ( цикл iз параметром ), i керувальна змiнна пробiжить значення вiд 1 до n то доведеться виконати n крокiв алгоритму .
31