ალგორითმთა ანალიზი: განსხვავება გადახედვებს შორის
| [შეუმოწმებელი ვერსია] | [შეუმოწმებელი ვერსია] |
შიგთავსი ამოიშალა შიგთავსი დაემატა
No edit summary |
No edit summary |
||
ხაზი 1:
[[ფაილი:Binary_search_vs_Linear_search_example_svg.svg|მინი| მოცემულ დალაგებულ სიაში მოცემული ჩანაწერის მოსაძებნად შეიძლება გამოიყენოთ ორობითი და ხაზოვანი ძებნის ალგორითმები. წინადხსენებული ალგორითმების ანალიზი გვიჩვენებს, რომ ''n'' სიგრძის სიისთვის საჭიროა მაქსიმუმ log<sub>2</sub>(''n'') და ''n'' შემოწმების ნაბიჯი. მოცემულ მაგალითში, 33 ელემენტიან სიაში „''Morin, Arthur-ის“'' მოსაძებნად საჭიროა 5 მოქმედება ორობითი (აღნიშნულია {{გაფერადება|#008080|მწვანედ}}), ხოლო 28 მოქმედება ხაზოვანი ({{გაფერადება|#800080|იისფერი}}) ძიების გამოყენების შემთხვევაში. ]]
[[ფაილი:Comparison_computational_complexity.svg|მინი| ფუნქციათა გრაფიკები ხშირად გამოიყენება ალგორითმთა ანალიზში, გვიჩვენებს შემავალი მონაცემების ზომა ''n-''ს ოპერაციების რაოდენობა ''N-''თან მიმართებაში თითოეული ფუნქიისთვის. ]]
'''ალგორითმთა ანალიზი''' — [[ინფორმატიკა|კომპიუტერულ მეცნიერებაში]] ალგორითმთა გამოთვლითი სირთულის, ანუ მათი შესრულებისთვის საჭირო დროის, მეხსიერებისა და სხვა აუცილებელი რესურსების რაოდენობის განსაზღვრა. ჩვეულებრივ, ეს გულისხმობს [[ფუნქცია (მათემატიკა)|ფუნქციის]] განსაზღვრას, რომელიც აკავშირებს ალგორითმის შემავალი მონაცემების სიგრძესა და გადადგმული ნაბიჯების რაოდენობას (მისი დროით სირთულეს) ან მის მიერ გამოყენებული მეხსიერების სიდიდეს (მის სივრცით სირთულეს). ითვლება, რომ ალგორითმი ეფექტურია მაშინ, როდესაც ამ ფუნქციის მნიშვნელობები მცირეა, ან შემავალი მონაცემების ზრდასთან შედარებით, იზრდება ნელა.
ტერმინი „ალგორითმთა ანალიზი“ [[დონალდ კნუთი|დონალდ კნუთმა]] დააარსა.<ref>{{cite web|url=http://web.archive.org/web/20160828152021/http://www-cs-faculty.stanford.edu/~uno/news.html|title=Knuth: Recent News|date=28 August 2016|website=web.archive.org}}</ref> ალგორითმთა ანალიზი არის გამოთვლითი სირთულის თეორიის მნიშვნელოვანი ნაწილი, რომელიც ითვალისწინებს თეორიულ შეფასებებს ნებისმიერი ალგორითმისთვის საჭირო რესურსებისთვის, რაც ხსნის მოცემულ გამოთვლით პრობლემას. ამ შეფასებებში მოცემულია ეფექტური ალგორითმების ძიების გონივრული საშუალებები.
| |||