დიდი-O ჩაწერა

დიდ-Θ ნოტაციას ვიყენებთ მუშაობის დროის ზრდის ასიმპტოტურად ზემოდან და ქვემოდან შემოსაზღვრისთვის მუდმივი მამრავლების სიზუსტით. ზოგჯერ მხოლოდ ზემოდან გვსურს შემოსაზღვრა.

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

კარგი იქნებოდა, გვქონოდა ისეთი ფორმის ასიმპტოტური ნოტაცია, რომელიც ამბობს: „მუშაობის დრო იზრდება მაქსიმუმ ამ მნიშვნელობამდე, მაგრამ, შეიძლება, უფრო ნელა გაიზარდოს.“ ამისათვის ვიყენებთ „დიდ-O“ ნოტაციას.

თუ მუშაობის დრო არის $O(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, მაშინ საკმარისად დიდი $n$n-ისთვის, მუშაობის დრო არის მაქსიმუმ $k \cdot f(n)$k, dot, f, left parenthesis, n, right parenthesis მუდმივა $k$k-სთვის. აი, როგორ უნდა ვიფიქროთ მუშაობის დროზე, რომელიც არის $O(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis:

ვამბობთ, რომ მუშაობის დრო არის „$f(n)$f, left parenthesis, n, right parenthesis-ის დიდი-O“, ან უბრალოდ „$f(n)$f, left parenthesis, n, right parenthesis-ის O“. დიდ-O-ს ნოტაციას ვიყენებთ ასიმპტოტური ზედა ზღვრებისთვის, რადგან ის ზემოდან საზღვრავს მუშაობის დროის ზრდას შემომავალი მონაცემების საკმარისად დიდი ზომებისთვის.

ახლა შეგვიძლია, ორობითი ძებნის მუშაობის დრო დავახასიათოთ ყველა შემთხვევისათვის. შეგვიძლია, ვთქვათ, რომ ორობითი ძებნის მუშაობის დრო ყოველთვის არის $O(\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis. შეგვიძლია, უფრო ძლიერი დებულებაც ვთქვათ მუშაობის დროის ყველაზე უარესი შემთხვევისათვის: ის არის $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis. მაგრამ ყველაფრის დამფარავი დებულება, რომლის თქმაც შეგვიძლია, არის ის, რომ ორობითი ძებნა მუშაობს $O(\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis დროში.

თუ დიდი-Θ ნოტაციის განსაზღვრებას გადახედავთ, შეამჩნევთ, რომ ძალიან ჰგავს დიდ-O ნოტაციას, იმ განსხვავებით, რომ დიდი-Θ ნოტაცია შემოსაზღვრავს ფუნქციას როგორც ზემოდან, ისე ქვემოდან (დიდი-O შემოსაზღვრავს მხოლოდ ზემოდან). თუ ვიტყვით, რომ მუშაობის დრო არის $\Theta(f(n))$\Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis კონკრეტულ სიტუაციაში, მაშინ ის ასევე არის $O(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis. მაგალითად, შეგვიძლია, ვთქვათ, რომ ვინაიდან ორობითი ძებნის მუშაობის დროის ყველაზე უარესი შემთხვევა არის $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis, ის ასევე არის $O(\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis.

შებრუნებული არ არის აუცილებლად ჭეშმარიტი: როგორც ვნახეთ, შეგვიძლია, ვთქვათ, რომ ორობითი ძებნა ყოველთვის მუშაობს $O(\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis დროში, მაგრამ ყოველთვის არ შეგვიძლია იმის თქმა, რომ ის მუშაობს ყოველთვის $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis დროში.

ვინაიდან დიდი-O-ს ნოტაცია გვაძლევს მხოლოდ ასიმპტოტურ ზედა ზღვარს და არა ასიმპტოტურად მჭიდრო ზღვარს, შეგვიძლია, გავაკეთოთ ისეთი დებულებები, რომლებიც ერთი შეხედვით მცდარი ჩანს, მაგრამ ტექნიკურად ჭეშმარიტია. მაგალითად, აბსოლუტურად ჭეშმარიტია, რომ ორობითი ძებნა მუშაობს $O(n)$O, left parenthesis, n, right parenthesis დროში. ეს იმიტომ, რომ მუშაობის დრო არ იზრდება უფრო ჩქარა, ვიდრე მუდმივა გამრავლებული $n$n-ზე. მეტიც, ის უფრო ნელა იზრდება.

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

ერთი მილიონი დოლარი არის 10 დოლარის ზედა ზღვარი ისევე, როგორც $O(n)$O, left parenthesis, n, right parenthesis არის ორობითი ძებნის მუშაობის დროის ზედა ზღვარი. სხვა (არამჭიდრო) ზედა ზღვრები ორობით ძებნაზე იქნებოდა $O(n^2)$O, left parenthesis, n, squared, right parenthesis, $O(n^3)$O, left parenthesis, n, cubed, right parenthesis და $O(2^n)$O, left parenthesis, 2, start superscript, n, end superscript, right parenthesis. მაგრამ არც $\Theta(n)$\Theta, left parenthesis, n, right parenthesis, არც $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis, არც $\Theta(n^3)$\Theta, left parenthesis, n, cubed, right parenthesis და არც $\Theta(2^n)$\Theta, left parenthesis, 2, start superscript, n, end superscript, right parenthesis არ იქნებოდა სწორი ორობითი ძებნის მუშაობის დროის აღსაწერად არცერთ შემთხვევაში.

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