ასიმპტოტური ჩანაწერი

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

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

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

მეორე იდეა არის შემდეგი: ყურადღება უნდა გავამახვილოთ იმაზე, თუ რამდენად სწრაფად იზრდება ფუნქცია მისი შემომავალი მონაცემების ზომის ზრდასთან ერთად. ამას ზრდის სიჩქარეს ვეძახით. ყველაფერი ძალიან რომ გავართულოთ, ფუნქცია უნდა გავამარტივოთ, რათა თვალ-ყური ვადევნოთ მეტად მნიშვნელოვან ნაწილს და მოვიშოროთ ნაკლებ მნიშვნელოვანი ნაწილები. მაგალითად, ვთქვათ, ალგორითმი, რომელიც $n$n ზომის მქონე შემომავალ მონაცემებზე მუშაობს, იყენებს $6n^2 + 100n + 300$6, n, squared, plus, 100, n, plus, 300 მანქანურ ინსტრუქციას. $6n^2$6, n, squared ხდება უფრო დიდი, ვიდრე დანარჩენი წევრები, $100 n + 300$100, n, plus, 300, როგორც კი $n$n ხდება საკმარისად დიდი, ამ შემთხვევაში - 20. აი, დიაგრამა, რომელიც გაჩვენებთ $6n^2$6, n, squared-სა და $100n + 300$100, n, plus, 300-ს $n$n-ის მნიშვნელობებისთვის 0-იდან 100-მდე:

ჩვენ ვიტყოდით, რომ ეს ალგორითმი მუშაობს $n^2$n, squared დროში, ვიშორებთ კოეფიციენტ 6-ს და დანარჩენ წევრებს: $100n + 300$100, n, plus, 300. მნიშვნელობა არა აქვს, რა კოეფიციენტებს ვიყენებთ; თუ მუშაობის დრო არის $an^2 + bn + c$a, n, squared, plus, b, n, plus, c რიცხვებისთვის $a > 0$a, is greater than, 0, $b$b და $c$c, ყოველთვის იარსებებს ისეთი მნიშვნელობა $n$n, რომლისთვისაც $an^2$a, n, squared არის მეტი, ვიდრე $bn + c$b, n, plus, c და ეს სხვაობა იზრდება, როცა $n$n იზრდება. მაგალითად, აი, დიაგრამა, რომელზეც ნაჩვენებია $0.6n^2$0, point, 6, n, squared-ისა და $1000n + 3000$1000, n, plus, 3000-ის მნიშვნელობები, სადაც ჩვენ $n^2$n, squared-ის კოეფიციენტი 10-ჯერ შევამცირეთ და დანარჩენი ორი კოეფიციენტი გავზარდეთ 10-ჯერ:

$n$n-ის მნიშვნელობა, რომელზეც $0.6n^2$0, point, 6, n, squared ხდება უფრო დიდი, ვიდრე $1000n + 3000$1000, n, plus, 3000, გაიზარდა, მაგრამ ასეთი გადაკვეთის წერტილი ყოველთვის იქნება, განურჩევლად იმისა, თუ რა შეზღუდვები გვაქვს.

მუდმივი კოეფიციენტებისა და ნაკლებად მნიშვნელოვანი წევრების მოშორებით შეგვიძლია ყურადღება გავამახვილოთ ალგორითმის მუშაობის დროის მნიშვნელოვან ნაწილზე — მისი ზრდის სიჩქარეზე — თან თავიდან ავირიდებთ ზედმეტ დეტალებში ჩასვლას, რომელიც აღქმას გვირთულებს. როდესაც ვიშორებთ მუდმივ კოეფიციენტებს და ნაკლებად მნიშვნელოვან წევრებს, შეგვიძლია, გამოვიყენოთ ასიმპტოტური ნოტაცია. მის სამნაირ ფორმას ვიხილავთ: big-$\Theta$\Theta ნოტაცია, big-O ნოტაცია და big-$\Omega$\Omega ნოტაცია.

ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტერული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.