ფუნქციები ასიმპტოტურ ჩანაწერში

როდესაც ალგორითმის მუშაობის დროის ზრდის ტემპს შემომავალი მონაცემის ზომა $n$‍-ის მიხედვით გამოვსახავთ და ამისათვის ასიმპტოტურ ნოტაციას ვიყენებთ, კარგი იქნება, თუ რაღაცებს გავითვალისწინებთ.

Let's start with something easy. Suppose that an algorithm took a constant amount of time, regardless of the input size. For example, if you were given an array that is already sorted into increasing order and you had to find the minimum element, it would take constant time, since the minimum element must be at index 0. Since we like to use a function of $n$‍ in asymptotic notation, you could say that this algorithm runs in $\mathrm{\Theta }(n^0)$‍ time. რატომ? Because $n^0=1$‍, and the algorithm's running time is within some constant factor of 1. In practice, we don't write $\mathrm{\Theta }(n^0)$‍, however; we write $\mathrm{\Theta }(1)$‍.

ახლა წარმოიდგინეთ, რომ ალგორითმს დასჭირდა $\mathrm{\Theta }({\log }_{10}n)$‍ დრო. აგრეთვე შეგიძლიათ, თქვათ, რომ მას დასჭირდა $\mathrm{\Theta }({\log }_{2}n)$‍ დრო. როდესაც ლოგარითმის ფუძე არის მუდმივი, მნიშვნელობა არა აქვს, რა ფუძეს გამოვიყენებთ ასიმპტოტურ ნოტაციაში. რატომ? რადგან არსებობს მათემატიკური ფორმულა, რომელიც ამბობს

ყველა დადებითი რიცხვისთვის $a$‍, $b$‍ და $n$‍. ასე რომ, თუ $a$‍ და $b$‍ ორივე მუდმივაა, მაშინ ${\log }_{a}n$‍ და ${\log }_{b}n$‍ განსხვავდება მხოლოდ ${\log }_{b}a$‍-თი და ეს მუდმივი მამრავლია, რომლის უგულებელყოფაც შეგვიძლია ასიმპტოტურ ნოტაციაში.

მაშასადამე, შეგვიძლია, ვთქვათ, რომ ორობითი ძებნის ყველაზე უარესი სამუშაო დრო არის $\mathrm{\Theta }({\log }_{a}n)$‍ ნებისმიერი დადებითი მუდმივა $a$‍-სთვის. რატომ? ვარაუდების რაოდენობა არის მაქსიმუმ ${\log }_{2}n+1$‍, თითოეული ვარაუდის გენერაცია და შემოწმება საჭიროებს მუდმივ დროს, შექმნა და დაბრუნება საჭიროებს მუდმივ დროს. თუმცა, პრაქტიკაში ხშირად ვწერთ, რომ ორობით ძებნას ესაჭიროება $\mathrm{\Theta }({\log }_{2}n)$‍, რადგან კომპიუტერულ მეცნიერებს უყვართ 2-ის ხარისხებში ფიქრი.

როცა ალგორითმებს ასიმპტოტურად ვაანალიზებთ, უნდა ვიცოდეთ ხშირად შემხვედრ ფუნქციებზე არსებული წესები. თუ $a$‍ და $b$‍ მუდმივებია და $a<b$‍, მაშინ $\mathrm{\Theta }(n^a)$‍-ს სამუშაო დრო იზრდება უფრო ნელა, ვიდრე $\mathrm{\Theta }(n^b)$‍-ს სამუშაო დრო. მაგალითად, $\mathrm{\Theta }(n)$‍-ის სამუშაო დრო, რომელიც არის $\mathrm{\Theta }(n^1)$‍, იზრდება უფრო ნელა, ვიდრე $\mathrm{\Theta }(n^2)$‍-ს სამუშაო დრო. არ არის აუცილებელი, რომ ხარისხის მაჩვენებლები იყვნენ მთელი რიცხვები. მაგალითად, $\mathrm{\Theta }(n^2)$‍-ს მუშაობის დრო იზრდება უფრო ნელა, ვიდრე $\mathrm{\Theta }(n^2\sqrt{n})$‍-ს მუშაობის დრო, რომელიც არის $\mathrm{\Theta }(n^{2.5})$‍.

შემდეგი გრაფი ადარებს $n$‍-ის,$n^2$‍-ისა და $n^{2.5}$‍-ის ზრდას:

ლოგარითმები უფრო ნელა იზრდებიან, ვიდრე მრავალწევრები. ანუ, $\mathrm{\Theta }({\log }_{2}n)$‍ იზრდება უფრო ნელა, ვიდრე $\mathrm{\Theta }(n^a)$‍ ნებისმიერი დადებითი მუდმივი $a$‍-სთვის. მაგრამ, ვინაიდან ${\log }_{2}n$‍-ის მნიშვნელობა იზრდება $n$‍-ის ზრდასთან ერთად, $\mathrm{\Theta }({\log }_{2}n)$‍ იზრდება უფრო სწრაფად, ვიდრე $\mathrm{\Theta }(1)$‍.

შემდეგი გრაფი ადარებს $1$‍-ის, $n$‍-ისა და ${\log }_{2}n$‍:-ის ზრდას:

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

აღვნიშნოთ, რომ მაჩვენებლიანი ფუნქცია $a^n$‍, სადაც $a>1$‍, იზრდება უფრო სწრაფად, ვიდრე მრავალწევრა ფუნქცია $n^b$‍, სადაც $b$‍ არის ნებისმიერი მუდმივა.

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

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