რა არის ორობითი ძიების დიდი O?

2024 ავტორი: Lynn Donovan | [email protected]. ბოლოს შეცვლილი: 2023-12-15 23:49

ორობითი ძებნა უფრო სწრაფია ვიდრე ხაზოვანი ძებნა მცირე მასივების გარდა.

ორობითი ძებნა ალგორითმი.

აქედან გამომდინარე, რა არის ორობითი ძიების სირთულე?

ორობითი ძებნა გადის ყველაზე ცუდ ლოგარითმულ დროს, აკეთებს O(log n) შედარებებს, სადაც n არის მასივის ელემენტების რაოდენობა, O არის Big O აღნიშვნა და log არის ლოგარითმი. ორობითი ძებნა იღებს მუდმივ (O(1)) სივრცეს, რაც იმას ნიშნავს, რომ ალგორითმის მიერ აღებული სივრცე იგივეა მასივის ნებისმიერი რაოდენობის ელემენტისთვის.

გარდა ამისა, არის თუ არა ბინარული ძებნა ყველაზე სწრაფი? Კი და არა. დიახ, არიან ეძებს რომლებიც საშუალოდ უფრო სწრაფია ვიდრე ბისექცია ძებნა . მაგრამ მე მჯერა, რომ ისინი კვლავ O(lg N) არიან, მხოლოდ უფრო დაბალი მუდმივით. გსურთ მინიმუმამდე დაიყვანოთ თქვენი ელემენტის მოსაძებნად საჭირო დრო.

ანალოგიურად შეიძლება ვინმემ იკითხოს, როგორ წერთ ბინარულ ძიებას?

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

რა არის ორობითი ძიების დროის სირთულე?

ასე რომ, უნდა არსებობდეს გარკვეული ტიპის ქცევა, რომელსაც ალგორითმი აჩვენებს, რომ მიეცეს a სირთულე ლოგის ნ. ვნახოთ, როგორ მუშაობს. მას შემდეგ, რაც ბინარული ძებნა აქვს საუკეთესო შემთხვევის ეფექტურობა O(1) და უარეს შემთხვევაში (საშუალო შემთხვევა) ეფექტურობა O(log n), ჩვენ განვიხილავთ ყველაზე ცუდი შემთხვევის მაგალითს. განვიხილოთ 16 ელემენტისგან შემდგარი დახარისხებული მასივი.