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

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

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

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

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

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

ახლა შეგვიძლია, ორობითი ძებნის მუშაობის დრო დავახასიათოთ ყველა შემთხვევისათვის. შეგვიძლია, ვთქვათ, რომ ორობითი ძებნის მუშაობის დრო ყოველთვის არის $O({\log }_{2}n)$‍. შეგვიძლია, უფრო ძლიერი დებულებაც ვთქვათ მუშაობის დროის ყველაზე უარესი შემთხვევისათვის: ის არის $\mathrm{\Theta }({\log }_{2}n)$‍. მაგრამ ყველაფრის დამფარავი დებულება, რომლის თქმაც შეგვიძლია, არის ის, რომ ორობითი ძებნა მუშაობს $O({\log }_{2}n)$‍ დროში.

თუ დიდი-Θ ნოტაციის განსაზღვრებას გადახედავთ, შეამჩნევთ, რომ ძალიან ჰგავს დიდ-O ნოტაციას, იმ განსხვავებით, რომ დიდი-Θ ნოტაცია შემოსაზღვრავს ფუნქციას როგორც ზემოდან, ისე ქვემოდან (დიდი-O შემოსაზღვრავს მხოლოდ ზემოდან). თუ ვიტყვით, რომ მუშაობის დრო არის $\mathrm{\Theta }(f(n))$‍ კონკრეტულ სიტუაციაში, მაშინ ის ასევე არის $O(f(n))$‍. მაგალითად, შეგვიძლია, ვთქვათ, რომ ვინაიდან ორობითი ძებნის მუშაობის დროის ყველაზე უარესი შემთხვევა არის $\mathrm{\Theta }({\log }_{2}n)$‍, ის ასევე არის $O({\log }_{2}n)$‍.

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

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

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

ერთი მილიონი დოლარი არის 10 დოლარის ზედა ზღვარი ისევე, როგორც $O(n)$‍ არის ორობითი ძებნის მუშაობის დროის ზედა ზღვარი. სხვა (არამჭიდრო) ზედა ზღვრები ორობით ძებნაზე იქნებოდა $O(n^2)$‍, $O(n^3)$‍ და $O(2^n)$‍. მაგრამ არც $\mathrm{\Theta }(n)$‍, არც $\mathrm{\Theta }(n^2)$‍, არც $\mathrm{\Theta }(n^3)$‍ და არც $\mathrm{\Theta }(2^n)$‍ არ იქნებოდა სწორი ორობითი ძებნის მუშაობის დროის აღსაწერად არცერთ შემთხვევაში.

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