|
[[ფაილი:Binary_search_vs_Linear_search_example_svg.svg|მინი| მოცემულ დავალებულდალაგებულ სიაში მოცემული ჩანაწერის მოსაძებნად შეიძლება გამოიყენოთ ორობითი და ხაზოვანი ძებნის ალგორითმი (რომელიც უგულებელყოფს შეკვეთას)ალგორითმები. ყოფილიწინადხსენებული დაალგორითმების უკანასკნელი ალგორითმის ანალიზითანალიზი გვიჩვენებს, რომ იგი''n'' იღებსსიგრძის სიისთვის საჭიროა მაქსიმუმ log <sub>2</sub> ( ''n'' ) და ''n'' შემოწმების ნაბიჯებს,ნაბიჯი. მოცემულ შესაბამისადმაგალითში, ''n'' სიგრძის ნუსხაში. 33 სიგრძის ასახულ მაგალითთაელემენტიან სიაში, „''"მორინიMorin, არტური"Arthur-ის“'' ეძებსმოსაძებნად საჭიროა 5 და 28 ნაბიჯს,მოქმედება ორობითი (ნაჩვენებიაღნიშნულია {{გაფერადება|#008080|cyanმწვანედ}} ), დახოლო 28 მოქმედება ხაზოვანი ( {{გაფერადება|#800080|magentaიისფერი}} ) ძიებით,ძიების გამოყენების შესაბამისადშემთხვევაში. ]]
[[ფაილი:Comparison_computational_complexity.svg|მინი| ფუნქციათა გრაფიკები ხშირად გამოიყენება ალგორითმთა ანალიზში, გვიჩვენებს შემავალი მონაცემების ზომა ''n-''ს ოპერაციების რაოდენობა ''N-''თან მიმართებაში თითოეული ფუნქიისთვის. ]]
'''ალგორითმთა ანალიზი''' --— [[ინფორმატიკა|კომპიუტერულ მეცნიერებაში]] ალგორითმთა გამოთვლითი სირთულის, ანუ მათი შესრულებისთვის საჭირო დროის, მეხსიერებისა და სხვა აუცილებელი რესურსების რაოდენობის განსაზღვრა. ჩვეულებრივ, ეს გულისხმობს [[ფუნქცია (მათემატიკა)|ფუნქციის]] განსაზღვრას, რომელიც აკავშირებს ალგორითმის შემავალი მონაცემების სიგრძესა და გადადგმული ნაბიჯების რაოდენობას (მისი დროით სირთულეს) ან მის მიერ გამოყენებული მეხსიერების სიდიდეს (მის სივრცით სირთულეს). ითვლება, რომ ალგორითმი ეფექტურია მაშინ, როდესაც ამ ფუნქციის მნიშვნელობები მცირეა, ან შემავალი მონაცემების ზრდასთან შედარებით, იზრდება ნელა. ერთიდაიგივე სიგრძის სხვადასხვა შემავალმა მონაცემებმა შეიძლება ალგორითმის განსხვავებული ქცევა გამოიწვიოს, ამიტომ საუკეთესო, ყველაზე უარესი და საშუალო შემთხვევების აღწერილობები შესაძლოა საერთო ინტერესში შედიოდეს. როდესაც სხვაგვარად არ არის მითითებული, ალგორითმის შესრულების ამსახველი ფუნქცია, როგორც წესი, ზედა საზღვარია, რომელიც განისაზღვრება ყველაზე უარესი შემავალი მონაცემების ალგორითმისკენ.
ტერმინი „ალგორითმთა ანალიზი“ [[დონალდ კნუთი|დონალდ კნუთმა]] დააარსა. ალგორითმთა ანალიზი არის გამოთვლითი სირთულის თეორიის მნიშვნელოვანი ნაწილი, რომელიც ითვალისწინებს თეორიულ შეფასებებს ნებისმიერი ალგორითმისთვის საჭირო რესურსებისთვის, რაც ხსნის მოცემულ გამოთვლით პრობლემას. ამ შეფასებებში მოცემულია ეფექტური ალგორითმების ძიების გონივრული საშუალებები.
|
