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

როდესაც ალგორითმის მუშაობის დროის ზრდის ტემპს შემომავალი მონაცემის ზომა $n$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$n in asymptotic notation, you could say that this algorithm runs in $\Theta(n^0)$\Theta, left parenthesis, n, start superscript, 0, end superscript, right parenthesis time. რატომ? Because $n^0 = 1$n, start superscript, 0, end superscript, equals, 1, and the algorithm's running time is within some constant factor of 1. In practice, we don't write $\Theta(n^0)$\Theta, left parenthesis, n, start superscript, 0, end superscript, right parenthesis, however; we write $\Theta(1)$\Theta, left parenthesis, 1, right parenthesis.

ახლა წარმოიდგინეთ, რომ ალგორითმს დასჭირდა $\Theta(\log_{10} n)$\Theta, left parenthesis, log, start base, 10, end base, n, right parenthesis დრო. აგრეთვე შეგიძლიათ, თქვათ, რომ მას დასჭირდა $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis დრო. როდესაც ლოგარითმის ფუძე არის მუდმივი, მნიშვნელობა არა აქვს, რა ფუძეს გამოვიყენებთ ასიმპტოტურ ნოტაციაში. რატომ? რადგან არსებობს მათემატიკური ფორმულა, რომელიც ამბობს

ყველა დადებითი რიცხვისთვის $a$a, $b$b და $n$n. ასე რომ, თუ $a$a და $b$b ორივე მუდმივაა, მაშინ $\log_a n$log, start base, a, end base, n და $\log_b n$log, start base, b, end base, n განსხვავდება მხოლოდ $\log_b a$log, start base, b, end base, a-თი და ეს მუდმივი მამრავლია, რომლის უგულებელყოფაც შეგვიძლია ასიმპტოტურ ნოტაციაში.

მაშასადამე, შეგვიძლია, ვთქვათ, რომ ორობითი ძებნის ყველაზე უარესი სამუშაო დრო არის $\Theta(\log_a n)$\Theta, left parenthesis, log, start base, a, end base, n, right parenthesis ნებისმიერი დადებითი მუდმივა $a$a-სთვის. რატომ? ვარაუდების რაოდენობა არის მაქსიმუმ $\log_2 n + 1$log, start base, 2, end base, n, plus, 1, თითოეული ვარაუდის გენერაცია და შემოწმება საჭიროებს მუდმივ დროს, შექმნა და დაბრუნება საჭიროებს მუდმივ დროს. თუმცა, პრაქტიკაში ხშირად ვწერთ, რომ ორობით ძებნას ესაჭიროება $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis, რადგან კომპიუტერულ მეცნიერებს უყვართ 2-ის ხარისხებში ფიქრი.

როცა ალგორითმებს ასიმპტოტურად ვაანალიზებთ, უნდა ვიცოდეთ ხშირად შემხვედრ ფუნქციებზე არსებული წესები. თუ $a$a და $b$b მუდმივებია და $a < b$a, is less than, b, მაშინ $\Theta(n^a)$\Theta, left parenthesis, n, start superscript, a, end superscript, right parenthesis-ს სამუშაო დრო იზრდება უფრო ნელა, ვიდრე $\Theta(n^b)$\Theta, left parenthesis, n, start superscript, b, end superscript, right parenthesis-ს სამუშაო დრო. მაგალითად, $\Theta(n)$\Theta, left parenthesis, n, right parenthesis-ის სამუშაო დრო, რომელიც არის $\Theta(n^1)$\Theta, left parenthesis, n, start superscript, 1, end superscript, right parenthesis, იზრდება უფრო ნელა, ვიდრე $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis-ს სამუშაო დრო. არ არის აუცილებელი, რომ ხარისხის მაჩვენებლები იყვნენ მთელი რიცხვები. მაგალითად, $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis-ს მუშაობის დრო იზრდება უფრო ნელა, ვიდრე $\Theta(n^2 \sqrt{n})$\Theta, left parenthesis, n, squared, square root of, n, end square root, right parenthesis-ს მუშაობის დრო, რომელიც არის $\Theta(n^{2.5})$\Theta, left parenthesis, n, start superscript, 2, point, 5, end superscript, right parenthesis.

შემდეგი გრაფი ადარებს $n$n-ის,$n^2$n, squared-ისა და $n^{2.5}$n, start superscript, 2, point, 5, end superscript-ის ზრდას:

ლოგარითმები უფრო ნელა იზრდებიან, ვიდრე მრავალწევრები. ანუ, $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis იზრდება უფრო ნელა, ვიდრე $\Theta(n^a)$\Theta, left parenthesis, n, start superscript, a, end superscript, right parenthesis ნებისმიერი დადებითი მუდმივი $a$a-სთვის. მაგრამ, ვინაიდან $\log_2 n$log, start base, 2, end base, n-ის მნიშვნელობა იზრდება $n$n-ის ზრდასთან ერთად, $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis იზრდება უფრო სწრაფად, ვიდრე $\Theta(1)$\Theta, left parenthesis, 1, right parenthesis.

შემდეგი გრაფი ადარებს $1$1-ის, $n$n-ისა და $\log_2 n$log, start base, 2, end base, n:-ის ზრდას:

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

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

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

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