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