Алгарытмы і як прааналізаваць іх складанасць

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

Давайце даведаемся! :)

Што такое алгарытм?

Набор крокаў, неабходных для выканання задачы.

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

Напрыклад, вы думалі пра алгарытм, які выконвае наступныя задачы?

  • Чысціце зубы
  • Прымі ванну
  • Кухар
  • Едзьце на працу дадому

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

  1. Сядай у маю машыну
  2. Паедзьце да дома сябра, каб пакатацца
  3. Едзьце ў офіс, дзе працую
  4. Прыпаркуйце машыну на гаражы

Гэта набор крокаў (алгарытм), які мне трэба выканаць, каб выканаць гэтую задачу.

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

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

Напрыклад, як павінен выглядаць алгарытм, які выкарыстоўваюць Waze і Google Maps, той, які вылічвае лепшы маршрут паміж двума месцамі? Што з алгарытмам Netflix, які прапануе фільмы і серыялы на аснове таго, што вы глядзелі?

Асабіста я не мог вам сказаць. Аднак я ведаю, што яны эфектыўныя. І эфектыўнасць - гэта стандарт, які мы выкарыстоўваем для аналізу складанасці алгарытму.

Што такое складанасць алгарытму?

У інфарматыцы складанасць алгарытму называе тое, колькі часу і прасторы патрабуе алгарытм для выканання задачы ў залежнасці ад памеру яго ўводу.

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

Аналіз часовай складанасці дазваляе вызначыць, як будзе весці сябе алгарытм пры павелічэнні яго ўваходных элементаў. Мы можам мець уяўленне пра час, якое спатрэбіцца для апрацоўкі 10, 100 ці 1000 элементаў.

І чаму гэты аналіз важны?

  • Вызначыць, які алгарытм найбольш эфектыўны;
  • Умець распрацоўваць больш эфектыўныя алгарытмы;
  • Для таго, каб прааналізаваць, ці эфектыўная бібліятэка алгарытму, ці нават мова на самай справе.

Падводзячы вынік, эфектыўнасць - гэта галоўнае!

Складанасць часу

Час, які патрабуецца для завяршэння дзейнасці.

Мы можам пачаць аналіз часу метадам падліку частоты, які ў асноўным падлічвае колькасць разоў, калі выконваецца машынная інструкцыя. Кожнаму этапу (інструкцыі) прызначаецца адзінка часу, пачынаючы з 1.

Час, які спажывае алгарытм, выражаецца функцыяй f (n), дзе n пазначае памер дадзеных.

Вынік аналізу выражаецца наступным чынам:

([функцыя, якая выражае час]) = [Сума адзінак часу]

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

Першая функцыя складаецца з двух цэлых лікаў:

Мы бачым, што для названай задачы рэалізаваны алгарытм выконвае толькі адзін крок: падвядзенне двух лікаў. Паколькі мы прыпісваем значэнне для кожнага кроку, вынік f (n) = 1.

Давайце разгледзім наступны прыклад - алгарытм, які дзеліць цэлае лік на іншае:

Нягледзячы на ​​тое, што гэта матэматычная аперацыя, падобная на падсумаванне, алгарытм змяшчае больш крокаў, таму што яму трэба праверыць, калі дзельнік роўны 0; у гэтым выпадку падзел не будзе рэалізаваны. Паколькі ў нас ёсць чатыры этапы, і кожнаму з іх прысвойваецца значэнне 1, вынік f (n) = 4.

Наступны алгарытм падводзіць усе элементы спісу цэлых лікаў:

У гэтым алгарытме адзін з этапаў ўключае ў сябе інструкцыю для паўтарэння; гэта азначае, што код ўнутры для будзе выкананы некалькі разоў. Паколькі колькасць выкананняў залежыць ад памеру дадзеных, мы прыпісваем значэнне n як адзінку часу. У выніку атрымаецца f (n) = 2n + 3.

Наступны алгарытм дадае суму аднаго спісу разам з сумай другога спісу.

У выніку маем f (n) = 2n² + 2n + 3.

Да гэтага часу мы бачылі толькі простыя алгарытмы, ці не так? А цяпер уявіце сабе аналіз больш складаных алгарытмаў і трэба правесці гэтыя вылічэнні? Не вельмі магчыма, так? Хоць гэта і падаецца найбольш прыдатным, ён вельмі карпатлівы і, у рэшце рэшт, гэтага не варта.

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

Напрыклад, які пераважны член сумы трэцяга алгарытму?

f (n) = 2n + 3

У гэтым выпадку пераважны тэрмін у 2 * n, і я растлумачу, чаму!

У любой сітуацыі, калі n перавышае 1 (n> 1), прадукт (вынік множання) ужо будзе каштаваць больш, чым другі член сумы.

Праверце што-небудзь: падставіце п на любое цэлае лік, большае за 1, і выканайце множанне.

Што наконт пераважнага члена сумы апошняга алгарытму?

f (n) = 2n² + 2n + 3

У гэтым выпадку пераважаючы тэрмін складае 2 * n², таму што пры n> 1 твор заўсёды будзе большым, чым другі і трэці члены сумы. Ідзі, выпрабуй!

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

Тут уступае ў дзеянне ордэн складанасці, таксама вядомы як Notation-O альбо Big-O.

Пазначэнне Big-O

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

Нотацыя Big-O таксама вызначае функцыю, якая выражае складанасць алгарытму ў часе. Для гэтага выкарыстоўваецца п як функцыя літары О.

Самыя распаўсюджаныя заняткі:

  • O (1) - Пастаяннае, колькасць аперацый не павялічваецца па меры павелічэння колькасці элементаў
  • O (log n) - лагарыфмічная, колькасць аперацый меншая за колькасць элементаў
  • O (n) - лінейная, колькасць аперацый павялічваецца прапарцыйна колькасці элементаў
  • O (n²) квадрата, колькасць аперацый будзе перавышаць колькасць элементаў
  • O (2 ^ n) - Экспаненцыяльная, колькасць аперацый хутка павялічваецца ў параўнанні з колькасцю элементаў
  • O (n!) - Фактарны, колькасць аперацый павялічваецца вельмі і вельмі хутка нават пры невялікай колькасці элементаў

Ніжэй мы маем графіку, якая ілюструе тэмп росту аперацый x Колькасць элементаў:

Графіка класіфікуецца наступным чынам:

  • Чырвоная зона страшная, пазбягайце гэтага!
  • Аранжавая зона дрэнна, таксама пазбягайце гэтага!
  • Жоўтая зона справядлівая, разумная!
  • Светла-зялёная зона добра, крута!
  • Цёмна-зялёная зона выдатная, віншую!

Зараз мы будзем выкарыстоўваць нотацыі Big-O для класіфікацыі згаданых раней алгарытмаў, якія заўсёды выкарыстоўваюць іх пераважны тэрмін.

Першы алгарытм прывёў да f (n) = 1; гэта азначае, што незалежна ад павелічэння элементаў алгарытм выконвае толькі адну аперацыю. Такім чынам, мы можам класіфікаваць алгарытм як Канстанты - O (1).

Другі алгарытм прывёў да f (n) = 4; гэта азначае, што незалежна ад павелічэння элементаў алгарытм будзе выконваць чатыры аперацыі. Такім чынам, мы можам таксама класіфікаваць гэты алгарытм як Канстанты - O (1).

Вынікам трэцяга алгарытму стаў f (n) = 2n + 3; гэта азначае, што колькасць аперацый будзе расці прапарцыйна колькасці элементаў, бачачы, як п выступае ў якасці зменнай у гэтай функцыі. Такім чынам, мы можам вызначыць гэты алгарытм як лінейны - O (n).

У выніку апошняга алгарытму атрымалася f (n) = 2n² + 2n + 3, гэта значыць, што колькасць аперацый павялічыцца больш, чым колькасць элементаў. У гэтым выпадку п таксама служыць пераменнай, але яна падымаецца да другой магутнасці (у квадраце). Такім чынам, мы можам вызначыць гэты алгарытм як квадратычны - O (n²).

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

Звярніце ўвагу, што ў экспанентным алгарытме 16 элементаў прывядуць да прынамсі 65,5536 аперацый. Даволі трывожна, праўда?

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

Некаторыя тэндэнцыі мы можам назіраць:

  • Алгарытмы, якія не маюць цыклу паўтарэння, як правіла, пастаянныя - O (1)
  • Алгарытмы, якія маюць завесы паўтарэння, пакуль яны не ўкладзеныя, як правіла, лінейныя - O (n)
  • Алгарытмы, якія маюць дзве ўкладзеныя завесы паўтарэння, як правіла, квадратныя - O (n²)
  • Прамы доступ да індэкса масіва звычайна O (1) (пастаянна)
  • Метады пашырэння спісу ў сярэднім складаюцца з O (n). Напрыклад: любы, сума і фільтр.
  • Алгарытмы сартавання, такія як Сартаванне бурбалак, Сартаванне ўстаўкі і Сартаванне выбару звычайна O (n²).

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

Я спадзяюся, што я дасягнуў мэты гэтага паста, які быў даць агляд алгарытмаў і іх аналіз з выкарыстаннем метадаў падліку частоты і Big-O.

Я пакінуў некалькі спасылак ніжэй як дадатковы матэрыял для чытання!

Літаратура:

Vídeos ад 1 да 1,7

Хочаце вывесці інавацыі на крэдытны рынак праз тэхналогіі? Мы заўсёды шукаем новых людзей, каб далучыцца да нашай здымачнай групы!

Праверце нашы праёмы тут.