§ 23. Паняцце правільнасці і складанасці алгарытму

23.1. Складанасць алгарытму

Асноўным паказчыкам складанасці (працаёмкасці) алгарытму з’яўляецца час, неабходны для рашэння задачы, і аб’ём патрэбнай памяці. Існуюць паняцці складанасці ў горшым і сярэднім выпадку. Звычайна ацэньваюць складанасць у горшым выпадку.

Часавая складанасць у горшым выпадку — функцыя ад памеру ўваходу, роўная максімальнай колькасці аперацый, выкананых у ходзе работы алгарытму пры рашэнні задачы дадзенага памеру.

Ёмістая складанасць у горшым выпадку — функцыя ад памеру ўваходу, роўная максімальнай колькасці памяці, да якой быў зварот пры рашэнні задач дадзенага памеру.

Пры аналізе складанасці для класа задач вызначаецца некаторы лік, які характарызуе аб’ём даных, што патрабуецца для ўяўлення ўваходных даных задачы. Гэта велічыня называецца памер уваходу. Можна зрабіць выснову, што складанасць алгарытму — функцыя памеру ўваходу. Памер уваходу можа залежаць як ад ліку ўваходных даных, так і ад велічыні ўваходных даных (прыклад 23.1).

Адным са спрошчаных відаў аналізу, што выкарыстоўваюцца на практыцы, з’яўляецца асімптатычны аналіз алгарытмаў. Мэтай асімптатычнага аналізу з’яўляецца параўнанне выдаткаў часу і іншых рэсурсаў розных алгарытмаў, прызначаных для рашэння адной і той жа задачы, пры вялікіх аб’ёмах уваходных даных.

Выкарыстоўваемая ў асімптатычным аналізе ацэнка функцыі працаёмкасці, якая называецца складанасцю алгарытму, дазваляе вызначыць, як хутка расце працаёмкасць алгарытму з павелічэннем аб’ёму даных.

У асімптатычным аналізе алгарытмаў выкарыстоўваюцца абазначэнні, прынятыя ў матэматычным асімптатычным аналізе.

Каб вызначыць зверху працаёмкасць алгарытму, выкарыстоўваецца абазначэнне O, чытаецца «о вялікае» (прыклад 23.2).

Часам пры аналізе алгарытму даводзіцца ўлічваць не толькі максімальную, але і мінімальную колькасць аперацый, неабходную для рашэння задачы. У гэтым выпадку выкарыстоўваецца абазначэнне  , чытаецца «амега».

Існуе шэраг важных практычных прычын для аналізу алгарытмаў. Адной з іх з’яўляецца неабходнасць атрымання ацэнак ці меж для аб’ёму памяці, ці часу работы, які спатрэбіцца алгарытму для паспяховай апрацоўкі пэўных даных. Машынны час і памяць — адносна дэфіцытныя (і дарагія) рэсурсы, на якія часта адначасова прэтэндуюць шмат якія карыстальнікі. Заўсёды трэба пазбягаць прагонаў праграмы, якія не прымаюцца сістэмай з прычыны недахопу запытанага часу. Тэарэтычны аналіз здольны выявіць вузкія месцы ў праграмах. 

Часам немагчыма скласці выразнае меркаванне пра адносную эфектыўнасць двух алгарытмаў. Адзін можа ў сярэднім лепш працаваць, да прыкладу, на выпадковых уваходных даных, у той час як іншы лепш працуе на нейкіх спецыяльных уваходных даных.

Будзем карыстацца наступным крытэрыем для ацэнкі якасці алгарытму: чым павольней расце функцыя f(n) на нейкім участку вобласці n, тым алгарытм будзе больш эфектыўным  (прыклад 23.3).

Этот критерий основан нГэты крытэрый заснаваны на часе работы ў горшым выпадку, але аналагічны крытэрый можа быць таксама вызначаны для сярэдняга часу работы.

При разработке алгоритма необходимо стремиться к тому, чтобы рост функции  f(n)  для алгоритма был как можно медленнее на той области, на которой требуется получить решение. Однако здесь могут возникать определенные трудностиПры распрацоўцы алгарытму неабходна імкнуцца да таго, каб рост функцыі f(n)  для алгарытму быў як мага больш павольным на той вобласці, на якой патрабуецца атрымаць рашэнне. Аднак тут могуць узнікаць пэўныя цяжкасці.

  1. Вельмі часта асобна ўзяты крок алгарытму можа быць выяўлены ў форме, якую цяжка перавесці непасрэдна ў канструкцыі мовы праграміравання.
  2. Канкрэтная рэалізацыя (выбар розных моў праграміравання і/ці розных структур даных) можа істотна ўплываць на патрабаванні да памяці і на хуткасць алгарытмуыбор различных языков программирования и/или различных структур данных) может существенно влиять на требования к памяти и на скорость алгоритма.

Прымер 23.1. Ацэнка складанасці пошукавых алгарытмаў.

Лінейны пошук

Знаходжанне інфармацыі ў неадсартаванай структуры даных, напрыклад у масіве, патрабуе ўжывання паслядоўнага пошуку. Паслядоўны пошук у сярэднім выпадку выканае праверку n/2 элементаў, а ў горшым — n элементаў. Пры гэтым мяркуецца, што параўнанне двух лікаў выконваецца за 1 аперацыю.

Бінарны пошук

Гэты метад пошуку значна эфектыўнейшы, чым паслядоўны пошук, але патрабуе, каб даныя былі папярэдне ўпарадкаваны (адсартаваны). У горшым выпадку выконваецца не больш за log2n, у сувязі з чым метад яшчэ называецца лагарыфмічным пошукам.

Няхай  — памер уваходных даных. Ацэнка складанасці алгарытму f(n) = 0(g(n)), калі пры g  > 0 і n  > 0 існуюць такія дадатныя C, n0, што f(n0) ≤ C * g(n0) .

Іншымі словамі, хуткасць росту функцыі пры дастаткова вялікіх  не вышэйшая за хуткасць росту функцыі.

Прымер 23.2. Ацэнка складанасці алгарытмаў сартавання.

Для метаду сартавання абменам ацэнка працаёмкасці складае  O(n2). Гэта азначае, што колькасць аперацый пры сартаванні n элементаў не пераўзыходзіць велічыню C · n2 пры некаторым значэнні каэфіцыента C, які не залежыць ад n.

Для быстрой сортировки оценка трудоемкости составляет в среднем — O(nlog2n). Гэта азначае, што колькасць аперацый пры сартаванні  элементаў не перавышае велічыню  C · nlog2n пры некаторым значэнні каэфіцыента C, які не залежыць ад n. Ацэнка ў горшым выпадку такая ж, як для сартавання абменам.

Няхай  — памер уваходных даных. Ацэнка складанасці алгарытму

f(n) =   (g(n)),

калі пры g > 0 і n > 0існуюць такія дадатныя c, n0, што

f(n0) ≥  c * g(n0),.

Іншымі словамі, хуткасць росту функцыі f пры дастаткова вялікіх n не ніжэйшая за хуткасць росту функцыі  g.

Пример 23.3. Магчымыя ацэнкі якасці алгарытму.

Канстантны алгарытм —  O(1)

Парадак росту O(1) азначае, што вылічальная складанасць алгарытму не залежыць ад памеру ўваходных даных. Адзінка ў формуле не значыць, што алгарытм выконваецца за адну аперацыю ці патрабуе вельмі мала часу. Важна тое, што гэты час не залежыць ад уваходных даных.

Лінейны алгарытм  — O(n)

Парадак росту O(n) азначае, што складанасць алгарытму лінейна расце з павелічэннем уваходнага масіву. Калі лінейны алгарытм апрацоўвае адзін элемент пяць мілісекунд, то мы можам чакаць, што тысячу элементаў ён апрацуе за пяць секунд. Напрыклад, лінейны пошук.

Лагарыфмічны алгарытм — O(n logn)

Парадак росту O (log n) азначае, што час выканання алгарытму расце лагарыфмічна з павелічэннем памеру ўваходнага масіву. Пры аналізе алгарытмаў па змоўчанні выкарыстоўваецца лагарыфм па аснове 2. Большасць алгарытмаў, якія працуюць па прынцыпе «дзялення папалам», маюць лагарыфмічную складанасць. Напрыклад, бінарны пошук.

Лінейна-лагарыфмічны алгарытм — O(nlogn)   

Лінейна-лагарыфмічны  алгарытм мае парадак росту O (n log n). Некаторыя алгарытмы тыпу «падзяляй і кіруй» трапляюць у гэту катэгорыю. Напрыклад, хуткае сартаванне (у сярэднім) або метад sort у STL.

Квадратычны алгарытм  — O(n2)

Час работы алгарытму з парадкам росту O(n2)  залежыць ад квадрата памеру ўваходных даных. Напрыклад, калі масіў з тысячы элементаў запатрабуе 1 000 000 аперацый, то масіў з мільёна элементаў запатрабуе 1 000 000 000 000 аперацый. Калі адна аперацыя патрабуе мілісекунду для выканання, квадратычны алгарытм будзе апрацоўваць мільён элементаў 32 гады. Напрыклад, сартаванне абменам.

Полінаміальны алгарытм — O(nk)

Пра полінаміальную складанасць (каля k) гавораць тады, калі час работы алгарытму расце не хутчэй, чым паліном k-й ступені ад  n.

Экспаненцыяльны алгарытм —  O(2n), O(en),  O(nn) и др.

Калі час работы алгарытму расце не павольней, чым экспанента ад n, то гавораць пра экспанентны алгарытм.

.