Основы объектно-ориентированного программирования на языке C# book | Page 30
2 Oснови алгоритмiзацiı̈
2.2 Складнiсть алгоритмiв
Природно, що перед розробкою програми слiд придумати, як розв’я-
зати поставлену задачу. При розробцi алгоритму необхiдно, перш за
все, придiлити увагу часу його роботи й обсягу пам’ятi, яку необхiдно
витратити для зберiгання й обробки даних. Данi подiляють на вхiдну
iнформацiю (вхiдне слово), тi, що вимагають промiжного зберiгання,
i вихiдну iнформацiю (вихiдне слово). Не всi данi вимагають одноча-
сного зберiгання й використання, а тому можна планувати роботу з
ефективного ı̈х використання.
Для розв’язання задачi можн а написати багато рiзних алгоритмiв.
Чим вони вiдрiзняються, який краще використовувати? Як визначити
поняття “краще” ? Такi питання виникають (або мають виникати) у
професiйного програмiста.
Для початку замiнимо поняття “краще” на “ефективнiше” й далi
його використовуватимемо. Ефективнiсть програми є дуже важливою
ı̈ı̈ характеристикою. Вона має двi складовi: розмiр i час.
Розмiр вимiрюється обсягом пам’ятi, що вимагається для виконан-
ня програми. Iнодi обсяг необхiдноı̈ пам’ятi є домiнуючим фактором в
оцiнцi ефективностi програми. Проте останнiми роками ця складова
ефективностi поступово втрачає своє значення.
Часова ефективнiсть програми визначається часом, необхiдним для
ı̈ı̈ виконання. Вона залежить як вiд конкретноı̈ реалiзацiı̈ алгоритму,
так i вiд власне вибраного алгоритму для розв’язання поставленоı̈
задачi.
Oтже, складнiсть обчислення, тобто роботи алгоритму на певно-
му вхiдному словi, визначається ресурсами, а ресурс, необхiдний для
конкретного обчислення, – це число. Знаходженням та оцiнкою такого
числа ми й займемося.
Oсновною властивiстю алгоритму є виконання поставленоı̈ задачi
за скiнченну кiлькiсть крокiв. Швидкiсть, з якою алгоритм викону-
ється на конкретному пристроı̈, може iстотно залежати вiд набору
вхiдних даних. При цьому швидкий у середньому алгоритм здатний
давати збоı̈ в окремих “поганих” випадках. I, якщо задача має на-
певно розв’язуватися за певний час роботи процесора, то ми вiддамо
перевагу алгоритму, повiльнiшому в середньому, проте надiйному в
гiрших ситуацiях. Саме умiння передбачати поганi ситуацiı̈ i вiдрi-
зняє квалiфiкованого алгоритмiста.
Будь-який крок алгоритму реалiзується деякою кiлькiстю машин-
них операцiй. Деталiзацiя алгоритму має бути такою, щоб на кожному
окремому кроцi не потрiбне було його подальше алгоритмiчне опра-
цьовування. Тут можливi лише двi ситуацiı̈: або фiксований час ви-
30