ალგორითმთა ანალიზი

ალგორითმთა ანალიზი — კომპიუტერულ მეცნიერებაში ალგორითმთა გამოთვლითი სირთულის, ანუ მათი შესრულებისთვის საჭირო დროის, მეხსიერებისა და სხვა აუცილებელი რესურსების რაოდენობის განსაზღვრა. ჩვეულებრივ, ეს გულისხმობს ფუნქციის განსაზღვრას, რომელიც აკავშირებს ალგორითმის შემავალი მონაცემების სიგრძესა და გადადგმული ნაბიჯების რაოდენობას (მისი დროით სირთულეს) ან მის მიერ გამოყენებული მეხსიერების სიდიდეს (მის სივრცით სირთულეს). ითვლება, რომ ალგორითმი ეფექტურია მაშინ, როდესაც ამ ფუნქციის მნიშვნელობები მცირეა, ან შემავალი მონაცემების ზრდასთან შედარებით, იზრდება ნელა. ერთი და იმავე სიგრძის სხვადასხვა შემავალმა მონაცემებმა შეიძლება ალგორითმის განსხვავებული ქცევა გამოიწვიოს, ამიტომ საუკეთესო, ყველაზე უარესი და საშუალო შემთხვევების აღწერილობები შესაძლოა საერთო ინტერესში შედიოდეს. როდესაც სხვაგვარად არ არის მითითებული, ალგორითმის შესრულების ამსახველი ფუნქცია, როგორც წესი, ზედა საზღვარია, რომელიც განისაზღვრება ყველაზე უარესი შემავალი მონაცემების ალგორითმისკენ.

მოცემულ დალაგებულ სიაში მოცემული ჩანაწერის მოსაძებნად შეიძლება გამოიყენოთ ორობითი და ხაზოვანი ძებნის ალგორითმები. წინადხსენებული ალგორითმების ანალიზი გვიჩვენებს, რომ n სიგრძის სიისთვის საჭიროა მაქსიმუმ log₂(n) და n შემოწმების ნაბიჯი. მოცემულ მაგალითში, 33 ელემენტიან სიაში „Morin, Arthur-ის“ მოსაძებნად საჭიროა 5 მოქმედება ორობითი (აღნიშნულია მწვანედ), ხოლო 28 მოქმედება ხაზოვანი (იისფერი) ძიების გამოყენების შემთხვევაში.

ფუნქციათა გრაფიკები ხშირად გამოიყენება ალგორითმთა ანალიზში, გვიჩვენებს შემავალი მონაცემების ზომა n-ს ოპერაციების რაოდენობა N-თან მიმართებაში თითოეული ფუნქიისთვის.

ტერმინი „ალგორითმთა ანალიზი“ დონალდ კნუთმა დააარსა. ალგორითმთა ანალიზი არის გამოთვლითი სირთულის თეორიის მნიშვნელოვანი ნაწილი, რომელიც ითვალისწინებს თეორიულ შეფასებებს ნებისმიერი ალგორითმისთვის საჭირო რესურსებისთვის, რაც ხსნის მოცემულ გამოთვლით პრობლემას. ამ შეფასებებში მოცემულია ეფექტური ალგორითმების ძიების გონივრული საშუალებები.

ალგორითმების თეორიულ ანალიზში ხშირია შეფასდეს მათი სირთულე ასიმპტომური გაგებით, ანუ შეფასდეს ფუნქციის სირთულე თვითნებურად დიდი შეყვანისთვის. ამ მიზნით გამოიყენება დიდი ო ნოტაცია, დიდი-ომეგა ნოტაცია და დიდი-თეტა ნოტაცია. მაგალითად, ორობითი ძებნის ნაბიჯების რაოდენობა პროპორციულია დალაგებული სიის გადარჩევისა, ან O (log(n))-ისა, კოლექტიურად „ლოგარითმულ დროში“. ჩვეულებრივ, ასიმპტომური შეფასებები გამოიყენება იმიტომ, რომ იგივე ალგორითმის სხვადასხვაგვარად განხორციელება შეიძლება განსხვავდებოდეს ეფექტურობაში. ამასთან ერთად, მოცემული ალგორითმის ნებისმიერი ორი „გონივრული“ განხორციელების ეფექტურობას უკავშირდება მუდმივი მრავლობითი ფაქტორი, რომელსაც ეწოდება ფარული მუდმივი .

ეფექტურობის ზუსტი (არაასიმპტომური) ზომები ზოგჯერ შეიძლება გამოითვალოს, მაგრამ ისინი ჩვეულებრივ მოითხოვენ გარკვეულ ალბათობით დაშვებებს ალგორითმის კონკრეტულ განხორციელებასთან დაკავშირებით, რასაც გამოთვლის მოდელი ეწოდება. გამოთვლის მოდელი შეიძლება განისაზღვროს აბსტრაქტული კომპიუტერის თვალსაზრისით, მაგალითად ტურინგის მანქანა, ან/და იმის მითითებით, რომ გარკვეული ოპერაციები ერთეულოვან დროში ხორციელდება. მაგალითად, თუ დალაგებულ სიას, რომელზეც ჩვენ ორობით ძებნას ვიყენებთ, აქვს n რაოდენობის ელემენტი და გვაქვს გარანტია, რომ სიაში არსებული ელემენტის მოძებნას ერთეულოვანი დრო დასჭირდება, მაშინ პასუხის მისაღებად დაგვჭირდება მაქსიმუმ log₂ n + 1 დროის ერთეული.