Особливості практичного застосування показників обчислювальної складності алгоритмів
Розглянута властивість обчислювальної складності алгоритмів. Уточнена термінологія. Розглянуті показники обчислювальної складності та методики їх визначення: класичні за Д. Кнутом та асимптотичні. Показані особливості інтерпретації цих показників. Виявлена можлива залежність показників обчислювально...
Saved in:
| Date: | 2008 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут програмних систем НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/1422 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Особливості практичного застосування показників обчислювальної складності алгоритмів / В.І. Шинкаренко // Пробл. програмув. — 2008. — N 2-3. — С. 57-63. — Бібліогр.: 53 назв. — укp. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860067362936455168 |
|---|---|
| author | Шинкаренко, В.І. |
| author_facet | Шинкаренко, В.І. |
| citation_txt | Особливості практичного застосування показників обчислювальної складності алгоритмів / В.І. Шинкаренко // Пробл. програмув. — 2008. — N 2-3. — С. 57-63. — Бібліогр.: 53 назв. — укp. |
| collection | DSpace DC |
| description | Розглянута властивість обчислювальної складності алгоритмів. Уточнена термінологія. Розглянуті показники обчислювальної складності та методики їх визначення: класичні за Д. Кнутом та асимптотичні. Показані особливості інтерпретації цих показників. Виявлена можлива залежність показників обчислювальної складності алгоритмів від обчислювальних пристроїв (ЕОМ), як можли-вості збільшення так і зниження. Показані проблеми та особливості визначення показників обчислювальної складності при алгори-тмічній реалізації наближених методів рішення задач. Особливості практичного застосування показників обчислювальної складності алгоритмів.
Property of computational complexity of algorithms is considered. Terminology is defined more accurately. Parameters of computational complexity and methods of their definition are considered: classical by D. Knuth and asymptotical. Peculiarity of interpretation of these pa-rameters is shown. Possible dependence of parameters of computational complexity of algorithms from executive devices (computer) is re-vealed, opportunities as increases and decrease. Problems and peculiarities of definition computational complexity parameters for algorithmic realization of approximated calculations are shown. Peculiarity of practical application of computational complexity parameters for algorithms.
|
| first_indexed | 2025-12-07T17:09:00Z |
| format | Article |
| fulltext |
Теоретичні та методологічні основи програмування
© В.І. Шинкаренко, 2008
ISSN 1727-4907. Проблеми програмування. 2008. № 2-3. Спеціальний випуск 57
УДК 004.051
ОСОБЛИВОСТІ ПРАКТИЧНОГО ЗАСТОСУВАННЯ ПОКАЗНИКІВ
ОБЧИСЛЮВАЛЬНОЇ СКЛАДНОСТІ АЛГОРИТМІВ
В.І. Шинкаренко
Дніпропетровський національний університет залізничного транспорту
ім. академіка В. Лазаряна
49010, Дніпропетровськ, вул. академіка Лазаряна, 2,
e-mail: ccp@diit-70.dp.ua
Розглянута властивість обчислювальної складності алгоритмів. Уточнена термінологія. Розглянуті показники обчислювальної
складності та методики їх визначення: класичні за Д. Кнутом та асимптотичні. Показані особливості інтерпретації цих показників.
Виявлена можлива залежність показників обчислювальної складності алгоритмів від обчислювальних пристроїв (ЕОМ), як можли-
вості збільшення так і зниження. Показані проблеми та особливості визначення показників обчислювальної складності при алгори-
тмічній реалізації наближених методів рішення задач. Особливості практичного застосування показників обчислювальної
складності алгоритмів.
Property of computational complexity of algorithms is considered. Terminology is defined more accurately. Parameters of computational
complexity and methods of their definition are considered: classical by D. Knuth and asymptotical. Peculiarity of interpretation of these pa-
rameters is shown. Possible dependence of parameters of computational complexity of algorithms from executive devices (computer) is re-
vealed, opportunities as increases and decrease. Problems and peculiarities of definition computational complexity parameters for
algorithmic realization of approximated calculations are shown. Peculiarity of practical application of computational complexity parameters
for algorithms.
Вступ
Для обґрунтованого застосування алгоритмів необхідно знати, а потім і вивчати їх властивості. Одна з
категорій властивостей складається з таких як: кількість операцій та операндів, кількість унікальних операцій
та операндів, обсяг програми (міри Холстеда) [1], цикломатична міра Мак-Кейба [2] та інші. Досить широкий
огляд таких властивостей надано в [3, 4]. Ця категорія властивостей вирізняється тим, що вони можуть бути
визначені за представленням алгоритмів та не потребують їх виконання. Самі властивості зазвичай визначають-
ся через відповідні показники.
Інша категорія властивостей алгоритмів – це властивості, які проявляються лише при виконанні алгори-
тмів або у багаторазовому виконанні. Такі властивості будемо вважати експлуатаційними характеристиками.
До них віднесемо часову та функціональну ефективність алгоритмів [5, 6].
Однією із найважливіших властивостей алгоритмів є обчислювальна складність (ОСА). Ця властивість
пов’язана з кількістю обчислень необхідних для досягнення результату.
Відразу розмежуємо обчислювальну складність як властивість алгоритмів і відповідні метрики та показ-
ники цієї властивості. До визначення показників ОСА є два принципово різних підходи: імовірнісний та статис-
тичний. Історично склалось так, що імовірнісний підхід, з’явившись першим став домінуючим у цьому питанні.
Зважаючи на те що властивість ОСА виявляється при виконанні алгоритмів, та її значущість саме при
виконанні, віднесемо цю властивість до сукупності експлуатаційних характеристик алгоритмів.
Кількість обчислень, а далі і обчислювальна складність залежить від вхідних даних. Тобто, якщо алго-
ритм реалізує відображення YX → (де X – множина вхідних даних, для кожного елемента якого алгоритм за
скінчений час має знайти результат, який є деяким елементом з Y), то існує деяке відображення:
NKKX ⊂→ , , (1)
де Kk ∈ – загальна кількість виконаних обчислювальних операцій для отримання елемента з Y за
заданими вхідними даними з X, або кількість кожної з операцій ( nNKk ⊂∈ ), якщо враховується різновид
операцій.
Властивість ОСА цілком характеризується відображенням (1), яке як показник цієї властивості не вико-
ристовується із деяких причин, насамперед через складність визначення. Наприклад, для алгоритмів сортування
в такому разі необхідно встановити залежність кількості обчислень від кількості та значень елементів, що під-
лягають сортуванню. Навіть для таких простих та досить добре досліджених алгоритмів це досить складна
задача.
Потрібні деякі інші показники ОСА (і вони існують), котрі можна визначити двояко: апріорно на основі
аналізу алгоритму і апостеріорно, підрахунком кількості обчислень під час його виконання. У даній роботі буде
розглянуто виключно першу можливість.
Навіщо потрібні показники обчислювальної складності? Безумовно вони опосередковано дають уявлення
про час виконання алгоритмів. Мабуть тому серед фахівців з теорії алгоритмів та розробників алгоритмів нема
одностайності у термінології. Одні в [7–13] цю властивість алгоритмів називають обчислювальною складністю
Теоретичні та методологічні основи програмування
58
(computational complexity), інші [14–20] – часовою складністю (time complexity), просто складністю – [21–32],
інакше, або ніяк не визначаючи властивість алгоритмів та виконують аналіз алгоритмів з визначенням часу або
кількості обчислень [33–47]. У роботі [15] для часових характеристик алгоритмів, мабуть вперше, застосовано
найбільш точний термін "часова ефективність". Для адекватного застосування суттєвостей, їх властивостей та
показників цих властивостей слід обережно поводитись з термінологією. Визначені терміни мають якнайкраще
відображати сутності. У даній роботі, поряд з іншим, аналізуються зазначені терміни та обґрунтовується їх за-
стосування.
Обчислення часу виконання алгоритму на конкретній ЕОМ за відомою кількістю застосовуваних опера-
цій неможливе через причини, пов’язані з багатьма засобами розгалуження обчислень такими як конвеєризація,
наявність декількох конвеєрів або процесорів, MMX – технологія тощо; непередбачуваністю часу виконання
допоміжних операцій, таких як доступ до даних з їх хешуванням [48–50]. Тому для властивості алгоритму по-
в'язаної з кількістю обчислень будемо вважати більш доцільним використання терміну "обчислювальна склад-
ність", а з часом виконання –"часова ефективність".
Безумовно обчислювальна складність є тією властивістю алгоритму, яка суттєво впливає на часову ефек-
тивність, але практичне значення останньої є незаперечно найбільш пріоритетне.
Наявність показників часової ефективності алгоритмів потребується двома задачами практичного про-
грамування. Перша полягає у виборі найбільш ефективного алгоритму з числа альтернативних при розробці
програмного забезпечення (ПЗ). Друга – розробка нових алгоритмів та визначення їх ефективності для визнання
їх придатності до застосування. Друга задача може виникнути й при розробці ПЗ, при відсутності потрібних
алгоритмів, або їх непридатності за низькою ефективністю.
Для обґрунтованого застосування методології слід знати та уважно ставитись до її об'єктивних обмежень
та особливостей. Метою даної роботи є дослідження можливості та обґрунтованості застосування імовірнісних
методів аналізу алгоритмів з визначення обчислювальної складності до оцінки їх часової ефективності в кон-
тексті вирішення саме цих задач програмування.
Для цього розглянуті існуючі методи дослідження та показники ОСА, які об'єднані у два напрями. Пер-
ший пов'язаний з підрахунком операцій, другий – з асимптотичними оцінками.
Аналіз алгоритмів за Д. Кнутом
Перший підхід до аналізу алгоритмів викладено у класичній роботі Д. Кнута 1972 р. [39]. Цьому переду-
вало чимало досліджень окремих алгоритмів, виконаних різними дослідниками в 1955 – 1970 рр., що свідчать
посилання Д. Кнута при аналізі алгоритмів [40].
Згідно Д. Кнута аналіз алгоритмів виконується таким чином:
− робляться деякі припущення щодо вхідних даних алгоритму. Наприклад, для алгоритмів сортування –
щодо кількості елементів у масиві, заповнення масиву (різними випадковими числами, чи з можливістю одна-
кових чисел, ступеня і порядку початкової відсортованості даних);
− для кожного кроку алгоритму, згідно обраних припущень, обчислюється кількість його виконання.
Обчислення ґрунтуються на теорії імовірностей та комбінаториці. Для деяких команд кількість повторів одна-
кова для кожного виконання алгоритму (можливо з деякими припущеннями щодо даних). Для інших команд
визначається четвірка: <мінімальна, середня та максимальна кількість разів виконання команди, та дисперсія до
середньої кількості > в залежності від кількості елементів даних;
− знаючи кількість повторів та час виконання кожного кроку нескладно обчислити час виконання алго-
ритму в цілому на конкретному комп'ютері. Д. Кнут приймає час виконання кожної команди деякої віртуальної
машини MIX одиницю – u, та визначає час виконання алгоритму в найгіршому, середньому та найкращому ви-
падках.
Приміром, час виконання алгоритму сортування пухирцем на машини MIX дорівнює < ;)18(:min uN +
;))log(75,7(: 2 uNNONave + uNN )15,05,7(:max 2 ++ .>
Особливості інтерпретації результатів. За сучасними уявленнями показником ОСА (для віртуальної
машини MIX) запропонована нечітка функція часу виконання алгоритму від кількості елементів даних. Тобто
аргументом функції є кількість елементів даних, а значенням – нечітке значення часу (min, ave, max) – класичне
трикутникове уявлення нечіткої величини.
Нечіткість пов’язана з невизначеністю властивостей даних ( для алгоритмів сортування ступеня початко-
вої відсортованості даних та їх порядку).
Зазначимо, що показники ОСА у вигляді нечіткої функції не дуже придатні для прийняття рішень і не ві-
дповідають вимогам до значень метрик якості програм. Згідно стандарту ISO/IEC 9126–2 рекомендовано засто-
совувати 5 видів шкал вимірювання значень [51]:
− номінальна шкала – розподілення значень за класами, наявність/відсутність деякої якості. Наприклад,
метрика, яка визначає наявність серед вхідних даних алгоритму імовірної величини. Ця метрика поділяє алго-
ритми на детерміновані та імовірнісні за обчислювальними методами;
− порядкова – дозволяє впорядкувати характеристики за будь-яким порядком;
− інтервальна – визначає "відстань" між характеристиками;
− відносна – значення розрізняються щодо обраної одиниці, або еталону;
Теоретичні та методологічні основи програмування
59
− абсолютна – визначає абсолютне значення характеристики.
Показник у вигляді нечіткої функції не відповідає ні одній з стандартизованих шкал.
Залежність обчислювальної складності від даних. Д Кнут зауважив, що "кожний метод має свої пере-
ваги та недоліки, тому він виявляється ефективнішим за інші при деяких конфігураціях даних і апаратури" [39]
(тут метод слід розуміти як алгоритм).
У сенсі сказаного розглянемо припущення при яких визначалися показники ОСА при дослідженні алго-
ритмів сортування.
Щодо даних вважається, що елементи є випадковими і різними. Те, що елементи є різними з точки зору
сортування записів з ключами відповідає більшості практичних випадків.
Але припустимо, що елементи є цілими числами ],0[ mai ∈ , де Mm << , M – кількість елементів масиву.
Звісно, що зменшення m призведе до зменшення ОСА більшості алгоритмів, а при m=0 (елементи однакові),
скажімо, для сортування пухирцем буде N порівнянь і нуль перестановок тобто, обчислювальна складність зна-
чно зменшиться.
Як бачимо, обчислювальна складність багатьох алгоритмів сортування залежить від початкового ступеня
відсортованості даних.
З цього зробимо висновок, що ОСА залежить не лише від кількості елементів, а і від них самих, тобто від
даних в цілому.
Залежність обчислювальної складності від виконавчих пристроїв. Щодо "апаратури" зроблено такі
припущення:
− всі команди виконуються однаковий час;
− час виконання команд не залежить від даних.
Друге припущення неявне (не зазначене Д. Кнутом) і витікає з першого.
Розглянемо друге припущення. Всі числа при обчисленнях на ЕОМ моделюються деякими модельними
числами. Так цілі числа можуть моделюватись 2, 4, 8 байтовими числами зі знаком або без нього. Розрядність
числа при цьому не залежить від його значення. Числа 5 і 31100, наприклад, будуть однаково представлені 16–
бітовими (2–байтовими) модельними числами. Час виконання конкретної операції над даними, представленими
однаковими модельними числами, однаковий.
Але уявимо, що значення елементів масиву ia – занадто великі і моделюються 16–байтовими числами.
Якщо ЕОМ не має команд обробки таких чисел, то обчислення виконуються з двома 8–байтовими за декілька
операцій. Подальше зростання значень ia призведе до моделювання 24, 32 … – байтовими числами і відповід-
но до зростання кількості операцій. Тобто чим більші модельні числа тим довші за часом відповідні операції, а
відтак і час виконання алгоритмів.
Це ще раз підтверджує тезу, що обчислювальна складність алгоритмів залежить від даних в цілому, а не
лише від їх кількості або обсягу.
З іншого боку, якщо ЕОМ має команди процесора з 8, 16, 32 … байтовими модельними числами, ОСА
залишиться незмінною при відповідному зростанні значень чисел.
Можуть бути заперечення: для порівняння 16 байтових чисел, необхідно два порівняння (з умовними пе-
реходами) 8–байтових, тобто треба змінити алгоритм.
Але, по–перше, алгоритм не відображає представлення даних, які проектуються при розробці програми
за наявним алгоритмом.
По–друге, відмітимо, що на мові програмування Ада модельні числа вибираються транслятором і відпо-
відно моделюються операції над ними: у випадку коли ЕОМ має операції обробки таких модельних чисел, тра-
нслятор використовує ці операції, коли не має – генерується відповідна послідовність команд для виконання
однієї операції. Алгоритм у вигляді програми на мові Ада ніяк це не відображає.
Наведені аргументи зазначають те, що кількість обчислень за алгоритмом (тобто ОСА) залежить від ви-
конавчого пристрою.
Ще один такий аргумент. Припустимо, що операції над розрядами чисел виконуються не так як на сучас-
них ЕОМ паралельно–послідовно, а суто послідовно, як це зазвичай виконується вручну. Однією операцією
буде операція над одним розрядом. Тоді кількість операцій буде залежати від розрядності елементів і обчислю-
вальна складність значно зросте.
Зважаючи на викладене можна говорити що неявні операції алгоритмів, які виконуються або можуть ви-
конуватись виконавчими пристроями, впливають на ОСА.
Отже, ОСА залежить від засобів виконання алгоритмів і при її визначенні слід враховувати ці
особливості.
Зв'язок між обчислювальною складністю та часовою ефективністю. Акцентуємо увагу на трьох мо-
ментах. По–перше, кінцевим призначенням аналізу алгоритмів Д. Кнут вважав обчислення часу виконання ал-
горитмів. По–друге, час виконання обчислюється для конкретного комп’ютера. Далі, Д. Кнут вважає, що
предметом області аналізу алгоритмів є визначення для заданого алгоритму його робочих характеристик. Хоча,
сенсом усієї роботи є саме аналіз алгоритмів, але самі робочі характеристики, а тим більш метрики їх виміру
ніяк не пойменовані і не визначені.
Д. Кнут визначав час виконання для віртуальної машини MIX, показово встановивши однаковим час ви-
конання всіх її команд. Це припущення не є обтяжливим: методика легко модифікується, якщо час виконання
Теоретичні та методологічні основи програмування
60
команд різний, але заздалегідь відомий. При тодішньому стані обчислювальної техніки такий підхід був обґру-
нтованим і не мав заперечень.
При сучасному стані обчислювальної техніки, з застосуванням різних засобів розгалуження обчислень,
час виконання команд не є постійним і може розглядатись лише як імовірнісна або нечітка величина.
Тому перехід від кількісних обчислень до часу не є прийнятним для сучасних ЕОМ. Водночас кількість
обчислень є об’єктивною характеристикою алгоритмів.
Асимптотичні показники обчислювальної складністі алгоритмів
Для визначення ступеня зростання ОСА при зростанні обсягів даних використовують асимптотичні по-
казники ОСА. Перш за все це показник точної асимптотичної оцінки, який як і в [41] позначимо ))(( ngΘ . Це
означає що знайдуться константи 0, 21 >cc та 0n такі, що )()()( 21 ngcnfngc ≤≤ при 0nn > . Де )(nf – показ-
ник ОСА, який підлягає оцінці, а )(ng – відповідна асимтотика. В якості )(ng за звичай беруться функції
nnnnnn 2,,),log(, 32
K . При цьому точна асимптотична оцінка поєднує в собі дві – верхню і нижню асимптоти-
чні оцінки.
Асимптотичні оцінки ОСА здебільшого, але не завжди співпадають з асимптотичними оцінками часу ви-
конання алгоритмів. Прискорення обчислень з причини розгалуження обчислень при конвеєрній обробці ко-
манд і виконанні на декількох процесорах не залежить від обсягів даних, що оброблюються.
Показники асимптотичної ОСА можна вважати метриками з порядковою шкалою. За нею алгоритми ро-
зподіляються на класи, які визначають потенційний час виконання алгоритмів при значних обсягах даних. На-
приклад, алгоритми сортування поділяються на класи з асимптотичною ОСА )( 2nΘ і )log(( nnΘ .
Найбільш корисною є класифікація за якою алгоритми розподілені на P алгоритми, тобто такі, що обчис-
лення за ними обмежені поліноміальною асимптотикою і NP – алгоритми, обчислення яких не обмежується
поліноміальною асимптотикою.
Асимптотичні показники ОСА розкривають потенційні можливості щодо кількості обчислень та часу ви-
конання алгоритмів за певних умов, а саме значного зростання обсягів даних, зменшенню похибок обчислень та
ін. Таке розподілення на класи є корисним для встановлення потенційної цінності алгоритму, потенційних мо-
жливостях його використанні в різноманітних ПЗ.
При вирішенні задачі вибору алгоритму, цей показник може бути корисним, якщо потреби конкретного
програмного засобу дійсно пов’язані зі значними вимогами до обсягів даних.
Якщо мається декілька альтернативних алгоритмів одного класу за асимптотичними показниками ОСА,
обґрунтований вибір серед них за цим показником неможливий, але він надає можливість звузити коло прийня-
тних алгоритмів.
Може здатися, що в цьому випадку може бути вирішальним допоміжний показник:
)(
)(
lim
ng
nf
i ∞→
=θ ,
де )(nf має асимптотичною ОСА ))(( ngΘ . Звісно алгоритм з показником 1=θ значно корисніший ніж
алгоритм з 1000=θ (при однаковій )(nΘ ). Тобто більш точно визначена асимптотика (оцінка за показником
)θ може впорядкувати алгоритми одної обчислювальної складності за )(nΘ .
Але для задач оцінки алгоритму, який щойно розроблено це мало що додає, а для задачі вибору алгорит-
му при близьких асимптотах також, зважаючи на перспективу наперед невизначеного впливу розгалуження
обчислень при їх виконанні на сучасних ЕОМ. Для багатьох алгоритмів асимптотичні показники є досить бли-
зькими, а різниця показника θ навіть у декілька разів може бути нівельована різним ступенем розгалуження
обчислень та ступенем хешування.
Розглянемо ситуацію, яка викладена у [52]. Деякий процесор має спеціалізований функціональний при-
стрій для якихось обчислень, наприклад, виразів вигляду ∑ ii xw , який виконує цю макрооперацію паралель-
но–послідовно.
Якщо в алгоритмі є цикл для обчислення зазначеної суми, то його обчислення має обчислювальну склад-
ність )(nΘ . Уявимо, що транслятор розпізнає такий цикл і перетворює у відповідну команду процесору і про-
цесор виконує лише одну команду (операцію). Тим самим транслятором та обчислювальним пристроєм ОСА
знижена до )1(Θ . Тобто наявний алгоритм і програма на різних обчислювальних пристроях може мати різну
обчислювальну складність.
Відмітимо також, що кількість паралельних операцій у спеціалізованому функціональному пристрої зав-
жди обмежена фізичними можливостями. Якщо обсяги даних перевищуватимуть можливості процесору заміна
циклу однією операцією буде неможлива, і подальше збільшення обсягів даних, все ж призведе до обчислюва-
льної складності )(nΘ . Але може статися так, що обсяг даних при всіх практичних застосуваннях дозволить
вищезазначену заміну. Тобто обчислювальна складність у практичному застосуванні буде )1(Θ .
Теоретичні та методологічні основи програмування
61
Підсумовуючи зазначимо можливу залежність асимптотичних показників ОСА від виконавчих
пристроїв.
Особливості обчислювальної складності алгоритмів наближених обчислень
Розглянемо обчислювальну складність алгоритмів наближених обчислень – методів знаходження кореня
алгебраїчного рівняння, скінчених різниць, кінцевих елементів тощо. ОСА є досить важливою характеристикою
для таких алгоритмів тому, що час їх виконання є достатньо великим навіть на сучасних ЕОМ і на кластерах.
Розглянемо алгоритм пошуку кореня рівняння з неперервною функцією за методом поділу відрізку на-
впіл, який показано псевдокодом.
Обчислювальна складність алгоритму визначається кількістю виконання циклу, яка дорівнює [53]:
1)/)((log2 −−≈ εabNц ,
а кількість обчислень алгоритму:
fA NabcN 5,1)/)((log2 ⋅−⋅≈ ε ,
де с – коефіцієнт, пов’язаний з обчисленням виразів у блоках 2 … 5, fN – обчислювальна складність функції
)(xf , яка може обчислюватись за формулою, рядами (і тоді обчислювальна складність обчислення функції бу-
де залежати від похибки обчислень) або іншим чином.
Як бачимо у випадку таких алгоритмів обчислювальна складність визначається вхідними даними ),,( εba
і ніяким чином не пов’язана з обсягами та кількістю вхідних даних. Показник асимптотичної ОСА визначається
за умов 0→ε .
Друга особливість: ОСА залежить від ОСА вкладеного (неявного) алгоритму обчислення функції.
Якщо ж функція у вигляді ряду обчислюється апаратно, то виявляється залежність ОСА і від виконавчо-
го пристрою.
Розглянемо дещо інший приклад. Припустимо, що мається алгоритм розв’язку задачі плоскої деформації
за методом кінцевих елементів. Вхідними даними є геометричний опис об'єкта дослідження у вигляді однієї або
декількох областей, їх фізичних властивостей, місця прикладання та значення зовнішніх сил, закріплення та
похибки. Алгоритм складається з чотирьох частин. У першій частині виконується розбиття областей на трикут-
никові елементи, у другій – формування системи лінійних алгебраїчних рівнянь, у третій – вирішення отрима-
ної системи рівнянь і в четвертій візуалізація або аналіз пласко–напруженого стану.
ОСА складається з обчислювальної складності частин, серед яких найбільш обтяжливим є розв’язок сис-
теми рівнянь. Це зважаючи на те що кількість кінцевих елементів може вимірюватись тисячами й більше. Аси-
мптотична ОСА алгоритму розв‘язку системи алгебраїчних рівнянь за методом Гауса )( 3nO . Але у даному
випадку вона значно менша за рахунок того, що матриця коефіцієнтів рівнянь є смугастою і переважна біль-
шість коефіцієнтів дорівнює нулю. Асимптотичний показник ОСА становить )( 2 nmO ⋅ , де n кількість рівнянь,
яка дорівнює подвоєній кількості вершин трикутників; m – ширина смуги з ненульових коефіцієнтів рівнянь. За
звичай m, що найменш на порядок менша за n.
обчислити )(afy a = (1)
цикл поки ε>− ab повторювати (2)
обчислити 2/)( bax += (3)
обчислити )(xfyx = (4)
якщо 0<∗ xa yy то (5)
обчислити xa = (6)
обчислити )(afy a = (7)
інакше
обчислити xb = (8)
кінець циклу
0=∀ ija
0=∀ ija
0≠ija
m n
Теоретичні та методологічні основи програмування
62
Ширина смуги визначається як:
)1(max2
),(
+−=
Γ∈
jim
ji
,
де i, j – номери вершин, Γ – множина ребер, кожне з яких визначається парою номерів вершин, які ребро
з’єднує.
Так, ширина смуги визначається вдалою нумерацією ребер. У випадку, як на рис. (а) оптимальною буде
нумерація вершин за рядками, на рис. (б) – також, у цьому випадку ширина смуги буде визначатись кількістю
вершин у рядку найбільш наближеного до діаметру.
При більш складній формі областей послідовність
нумерації наперед визначити занадто складно. Тому
частина формування системи рівнянь має застосову-
вати алгоритм нумерації для зменшення ширини
смуги.
Оптимальний розв‘язок задачі нумерації є
NP–повною задачею. Її розв‘язок при значній кіль-
кості вершин (навіть порядку тисячі) є неможливим
за прийнятний час. Тому алгоритм нумерації може
бути або евристичним, або стохастичним і не гаран-
тує оптимальності, але здатен реально значно змен-
шити ширину смуги.
Значення ширини смуги складно визначити
апріорно. Та й значення кількості рівнянь деколи
також, якщо сітка нерівномірна, а як того потребує
дотримання однакових похибок у різних частинах
області, густішає у місцях концентрації напружень
(рис. в).
Підсумовуючи, ОСА третьої частини алгори-
тму (й усього алгоритму) залежить від значень n, що
є результатом роботи першої частини алгоритму і m,
що є результатом другої частини. Безумовно, ОСА
всього алгоритму, як і інших, визначається вхідними даними, в першу чергу формою області та заданою похиб-
кою. Але, його ОСА залежить від того, наскільки вдало виконана нумерація вузлів. Тобто ОСА залежить від
функціональної ефективності [6] деякої частини алгоритму. Алгоритм має можливості впливати на свою ОСА.
Ще більш складною є ситуація щодо наближених стохастичних алгоритмів, наприклад генетичних алго-
ритмів. Автор не має відомостей щодо методів визначення показників ОСА для таких алгоритмів і практичного
визначення показників ОСА для будь–яких з них. Навіть можливість визначення показників ОСА для стохасти-
чних алгоритмів є під сумнівом.
Висновки
Обчислювальна складність алгоритму – провідний фактор, що визначає його часову ефективність. До-
сить важливою передумовою її використання є відсутність потреби виконання алгоритму для її визначення. Але
при застосуванні показників ОСА слід враховувати таке:
− при виборі алгоритму з числа альтернативних для застосування його в конкретному ПЗ можуть засто-
совуватись лише асимптотичні показники ОСА. Вони дозволяють визначити найбільш конкурентноздатні алго-
ритми. У випадку однакової асимптотичної ОСА ці показники не дозволяють розв’язати таку задачу взагалі;
− показники ОСА у вигляді нечіткої функції не відповідають вимогам стандартів щодо метрик якості;
− ОСА залежить від обчислювальних механізмів, на яких передбачається виконання алгоритмів. Реальна
ОСА може бути як знижена, так і підвищена засобами обчислювальних механізмів;
− ОСА може бути змінена алгоритмічно: функціональна ефективність однієї частини алгоритму може
суттєво впливати на ОСА іншої частини.
Крім того, зазначимо, що обчислювальна складність алгоритмів залежить від усієї множини вхідних да-
них. Залежність ОСА від обсягу вхідних даних слід розглядати як важливий типовий окремий випадок. Інший
типовий випадок – залежність ОСА від похибки наближених обчислень.
Стосовно термінології. Мабуть є сенс за термінологією розподілити характеристики алгоритмів такі:
− обчислювальна складність алгоритму (ОСА), як характеристика алгоритму, пов’язана з кількістю обчи-
слень при заданому представлені (зазначених у представленні операцій) для різних даних без урахування особ-
ливостей обчислювальних пристроїв. ОСА може бути визначена за представленням алгоритму;
Рисунок. Розрахункові схеми з розбиттям областей на
трикутникові скінчені елементи
б)
в)
а)
Теоретичні та методологічні основи програмування
63
− обчислювальна складність алгоритму орієнтованого на визначений обчислювальний пристрій або при-
строї (ОСА+П). Характеристика пов’язана з кількістю обчислень при заданому представлені для різних даних з
урахуванням набору примітивних операцій конкретних обчислювальних пристроїв;
− часова ефективність, як характеристика алгоритмів пов’язана з часом виконання алгоритму. Як окре-
мий випадок – на конкретних пристроях.
1. Холстед М.Х. Начало науки о программах. – М.: Финансы и статистика, 1981. – 128 с.
2. McCabe N.J. A complexity measure // IEEE Trans. Sofware Eng. – 1976. – Vol. SE – 2, № 4. – p. 308 – 320.
3. Черноножкин С.К. Меры сложности программ. – Новосибирск, 1994. – 35 с. (Препр. / Ин–т систем информатики СО РАН; 94 – 21).
4. Евстигнеев В.А., Кожевникова Г.П. Топологические меры сложности программ. – Новосибирск, 1989. – 30 с. (Препр. / Ин–т точной
механики и вычислительной техники. Новосибирский филиал; 89 – 23).
5. Шинкаренко В.И. Сравнительный анализ временной эффективности функционально эквивалентных алгоритмов // Проблемы про-
граммирования. – 2001. – № 3/4 – С. 31–39.
6. Шинкаренко В.И. Функциональная эффективность нечетко специфицированных алгоритмов // Проблемы программирования. – 2006. –
№ 1 . – С. 24–33.
7. Канаєва Н.М.. Дослідження локальних алгоритмів розв’язання блочних задач булевого програмування: Автореф. дис. … канд. фіз.–
мат. наук: 01.05.01 / Дніпропетровський держ. ун–т – Дніпропетровськ., 2000. – 16 с.
8. Катленд Н. Вычислимость. Введение в теорию вычислимых функций. – М.: Мир, 1983. – 256 с.
9. Ковтун И.В. Поиск части оптимальной разметки некоторого NP–полного подкласса (max,+) задач // Управляющие системы и машины.
– 2003. – № 6 . – С. 33–38.
10. Кожевникова Г.П. Структуры данных и проектирование эффективной вычислительной среды. – Львов: ЛГУ, 1986. – 176 с.
11. Макконнел Дж. Основы современных алгоритмов. – М.: Техносфера, 2004. – 368 с.
12. Stephens R. Ready–To–Run Visual Basic Algorithms. – Wiley Computer Publishing, 1998. – 448 p.
13. Tarjan R.E. Data structures and network algorithms. – Philadelphia: SIAM, 1983. – 131 p.
14. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. – 536 с.
15. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: Изд. дом "Вильямс", 2000. – 384 с.
16. Глибовець М.М. Основи комп'ютерних алгоритмів. – К.: Видав. дім "КМ Академія", 2003. – 452 с.
17. Зубов В.С. Справочник программиста. Базовые методы решения графовых задач и сортировки. – М.: Информ.–изд. дом "Филинъ",
1999. – 256 с.
18. Павлюк О.В., Савчинський Б.Д. Ефективний синтаксичний аналіз та розпізнавання структурованих зображень // Управляющие систе-
мы и машины. – 2005. – № 5 . – С. 13 – 24.
19. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. – М.: Наука, 1987. – 288 с.
20. Neapolitan R., Naimipour K. Foundations of Algorithms Using C++ Pseudocode, Third Edition. – Jones and Bartlett Publishers, 2004. – 618 p.
21. Анисимов А.В. Алгоритмы модулярной редукции // Проблемы программирования. – 1999. – № 1 – С. 80–91.
22. Василенко О.Н. Теоретико–числовые алгоритмы в криптографии. – М.: МЦНМО, 2003. – 328 с.
23. Винокур А.Б. Кожевникова Г.П. Формализованный анализ сложности алгоритмов иерархического типа на основе распознавания их
классификационных свойств. – Киев, 1986. – 30 с. (Препр. / Ин–т . кибернетики АН УССР; 86–9).
24. Гуц А.К. Математическая логика и теория алгоритмов: учебное пособие. – Омск: Изд. Наследие. Диалог–Сибирь, 2003
25. Зятьков Е.А. Алгоритм сложности O(nlogn) минимизации максимума линейных функций. – Минск, 1993. – 16 с. (Препр. / Ин–т техн.
кибернетики АН Белоруссии; 93 – 15).
26. Пападимитриу Х. Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир, 1984. – 510 с.
27. Сапоженко А.А. Некоторые вопросы сложности алгоритмов: Учебное пособие. – М.: Изд. отдел ВМиК МГУ, 2001. – 46 с.
28. Трауб Дж., Вожняковский Х. Общая теория оптимальных алгоритмов. – М.: Мир, 1983. – 382 с.
29. Черемушкин А.В. Лекции по арифметическим алгоритмам в криптографии. – М.: МЦНМО, 2002. – 104 с.
30. Harris S., Ross J. Beginning algorithms. – Indianapolis: Wiley Publishing, Inc., 2006. – 564 p.
31. Kreher D.L., Stinson D.R. Combinatorial algorithms: generation, enumeration and search. – N.Y.: CRC Press, 1999. – 329 p.
32. http://intsys.msu.ru/staff/vnosov/theoralg.htm Носов В.А. Основы теории алгоритмов и анализа их сложности. – М., 1992. – 144 с.
33. Абрамов С.А. Элементы анализа программ. Частичные функции на множестве состояний. – М.: Наука, 1986. – 128 с.
34. Анисимов А.В., Проценко В.С., Айрапетян Л.Р. Алгоритмы неоднородной сортировки. – Киев, 1979. – 22 с. (Препр. / Ин–т . кибернети-
ки АН УССР; 79–12).
35. Бекнелл Д.М. Фундаментальные алгоритмы и структуры данных в Delphi. – СПб.: ООО "ДиаСофтЮП", 2003 – 560 с.
36. Вирт Н. Алгоритмы + структуры данных = программа. – М.: Мир, 1985. – 406 с.
37. Грин Д., Кнут Д. Математические методы анализа алгоритмов. – М.: Мир, 1987. – 120 с.
38. Гудрич М.Т., Тамассия Р. Структуры данных и алгоритмы в Java . – Мн.: Новое знание, 2003. – 671 с.
39. Кнут Д. Э. Искусство программирования, том 1 // Основные алгоритмы. – М.: Изд. дом "Вильямс", 2000. – 720 с.
40. Кнут Д. Э. Искусство программирования, том 3 // Сортировка и поиск. – М.: Изд. дом "Вильямс", 2000. – 832 с.
41. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2001. – 960 с.
42. Макконелл Дж. Анализ алгоритмов. Вводный курс. – М.: Техносфера, 2002. – 304 с.
43. Пашко С.В. Субоптимальные алгоритмы выполнения булевых операций над мультиполигонами. Часть 2 // Проблемы управления и
информатики. – 2005. – № 3 – С. 60–75.
44. Седжвик Р. Фундаментальные алгоритмы на С. Анализ/Структуры данных/Сортировка/Поиск/Алгоритмы на графах. СПб: ООО "Ди-
аСофтЮП", 2003. – 1136 с.
45. Сетин А.А. О некоторых сложностных характеристиках неуниформных вычислений: Автореф. дис. … канд. физ.–мат. наук: 01.01.09 /
МГУ – М., 1992. – 9 с.
46. Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. – М.: Сов. радио, 1974. – 200 с.
47. Mahmoud H.M. Sorting. A distribution theory. – N.Y.: Wiley interscience publishing, Inc., 2000. – 394 p.
48. Касперски К. Техника оптимизации программ. Эффективное использование памяти. – СПб.: БХВ–Петербург, 2003. – 464 с.
49. Шинкаренко В.И. Зависимость временной эффективности алгоритмов и программ обработки больших объемов данных от их кэширо-
вания // Математические машины и системы. – 2007 – № 2. – С. 43–55.
50. Шинкаренко В.И. Временная оценка операций обработки структурированных данных с учетом конвейеризации и кэширования // Про-
блемы программирования. – 2006. – № 2–3 – С. 43–52.
51. Андон Ф.И., Коваль Г.И., Коротун Т. М., Лаврищева Е.М., Суслов В.Ю. Основы инженерии качества программных систем. – Киев:
Академпериодика, 2007. – 670 с.
52. Дорошенко А.Е., Рагозин Д.В. Использование комплексных функциональных устройств микропроцессоров при оптимизирующей ком-
пиляции // Управляющие системы и машины. – 2004. – № 2 . – С. 46–55.
53. Непомнящий В.А., Рякин О.М. Прикладные методы верификации программ / Под ред. А.П. Ершова. – М.: Радио и связь, 1988. – 256 с.
|
| id | nasplib_isofts_kiev_ua-123456789-1422 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Ukrainian |
| last_indexed | 2025-12-07T17:09:00Z |
| publishDate | 2008 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Шинкаренко, В.І. 2008-07-30T15:22:08Z 2008-07-30T15:22:08Z 2008 Особливості практичного застосування показників обчислювальної складності алгоритмів / В.І. Шинкаренко // Пробл. програмув. — 2008. — N 2-3. — С. 57-63. — Бібліогр.: 53 назв. — укp. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/1422 004.051 Розглянута властивість обчислювальної складності алгоритмів. Уточнена термінологія. Розглянуті показники обчислювальної складності та методики їх визначення: класичні за Д. Кнутом та асимптотичні. Показані особливості інтерпретації цих показників. Виявлена можлива залежність показників обчислювальної складності алгоритмів від обчислювальних пристроїв (ЕОМ), як можли-вості збільшення так і зниження. Показані проблеми та особливості визначення показників обчислювальної складності при алгори-тмічній реалізації наближених методів рішення задач. Особливості практичного застосування показників обчислювальної складності алгоритмів. Property of computational complexity of algorithms is considered. Terminology is defined more accurately. Parameters of computational complexity and methods of their definition are considered: classical by D. Knuth and asymptotical. Peculiarity of interpretation of these pa-rameters is shown. Possible dependence of parameters of computational complexity of algorithms from executive devices (computer) is re-vealed, opportunities as increases and decrease. Problems and peculiarities of definition computational complexity parameters for algorithmic realization of approximated calculations are shown. Peculiarity of practical application of computational complexity parameters for algorithms. uk Інститут програмних систем НАН України Теоретичні та методологічні основи програмування Особливості практичного застосування показників обчислювальної складності алгоритмів Peculiarity of practical application of computational complexity parameters for algorithms Article published earlier |
| spellingShingle | Особливості практичного застосування показників обчислювальної складності алгоритмів Шинкаренко, В.І. Теоретичні та методологічні основи програмування |
| title | Особливості практичного застосування показників обчислювальної складності алгоритмів |
| title_alt | Peculiarity of practical application of computational complexity parameters for algorithms |
| title_full | Особливості практичного застосування показників обчислювальної складності алгоритмів |
| title_fullStr | Особливості практичного застосування показників обчислювальної складності алгоритмів |
| title_full_unstemmed | Особливості практичного застосування показників обчислювальної складності алгоритмів |
| title_short | Особливості практичного застосування показників обчислювальної складності алгоритмів |
| title_sort | особливості практичного застосування показників обчислювальної складності алгоритмів |
| topic | Теоретичні та методологічні основи програмування |
| topic_facet | Теоретичні та методологічні основи програмування |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/1422 |
| work_keys_str_mv | AT šinkarenkoví osoblivostípraktičnogozastosuvannâpokaznikívobčislûvalʹnoískladnostíalgoritmív AT šinkarenkoví peculiarityofpracticalapplicationofcomputationalcomplexityparametersforalgorithms |