ერთ-ერთის შემოწმება
ხაზოვანი ძებნა: ყოველი მათგანი შემოწმება
წარმოიდგინეთ, რომ გაქვთ 10 კარტი სახეზე ჩახვეული, დაზღვეულია 1-დან 10-მდე, შემთხვევითი თანმიმდევრობით შერეული.
გსურთ იპოვოთ კარტი რიცხვით 7.
აბრუნებთ კარტებს ერთ-ერთის ქვემოთ, მარცხნიდან მარჯვნივ, სანამ მას წონა.
| სცენარი | ქვემოთი დაჭრილი |
|---|---|
| საუკეთესო შემთხვევა | 1 ქვემოთ დაჭრილი (იღბლიანი პირველი ცდა!) |
| ყველაზე ცუდი შემთხვევა | 10 ქვემოთ დაჭრილი (ეს იყო ბოლო კარტი) |
| საშუალო | დაახლოებით 5 ქვემოთ დაჭრილი |
ახლა წარმოიდგინეთ 100 კარტი. საშუალო: დაახლოებით 50 ქვემოთ დაჭრილი.
1000 კარტი? საშუალო: დაახლოებით 500 ქვემოთ დაჭრილი.
ნიმუშის დანახვა? კარტების გაორმაგება, მუშაობის გაორმაგება. მუშაობა სწორი ხაზით იზრდება.
კომპიუტერული მეცნიერების სპეციალისტები ამას ხაზოვანი ძებნა უწოდებენ — ხაზოვანი ნიშნავს, რომ მუშაობა იზრდება ხაზის მსგავსად: სტაბილური & წინასწარი.
ხაზოვანი ძებნა მუშაობს ნებისმიერ სიაზე, დახარისხებული ან არა. ეს ითავსებს მას მარტივ. მაგრამ შეიძლება ნელი იყოს.
რამდენი სახელი?
გაქვთ კლასის სია 20 სახელი შემთხვევითი თანმიმდევრობით დაწერილი.
უნდა იპოვოთ სახელი Zoe.
თქვენ სახელებს ერთ-ერთის ქვემოთ შეამოწმებთ, სიის ზემოდან ქვეთ.
სიის ნახევარი აჭრილი
ორობითი ძებნა: შუაგნამდე ხტება
ორობითი ძებნას აქვს ერთი წესი: სია ჯერ დახარისხებული უნდა იყოს.
თუ თქვენი 20 სახელის სია იწყება A-დან Z-მდე, შეგიძლიათ გამოიყენოთ ორობითი ძებნა.
როგორ მუშაობს: გახსენით შუა სახელამდე (სახელი #10). იკითხეთ: არის თუ არა Zoe ამ სახელიმდე ან მის შემდეგ?
Z ალფაბეტის ბოლო ნაწილშია, ამიტომ Zoe შუაგნაციდან შემდეგში მდებარეობს. გადააგდეთ პირველი ნახევარი. ახლა გაქვთ მხოლოდ სახელი 11-20 დარჩა.
შემოწმება 10 სახელის შუაგნაფი (სახელი #15). Z მოდის M-ის შემდეგ, ამიტომ Zoe ხვდება სახელი #15-ის შემდეგ. გადააგდეთ სახელი 11-14. ახლა გაქვთ სახელი 16-20 დარჩა.
გააგრძელეთ ნახევრად აჭრილი. თითოეული შემოწმება ამოკლებს დარჩენილი სახელების ნახევარს.
| სიის ზომა | მაქსიმალური შემოწმება ორობითი ძებნის დროს |
|---|---|
| 20 სახელი | მაქსიმუმ 5 შემოწმება |
| 1,000 სახელი | მაქსიმუმ 10 შემოწმება |
| 1,000,000 სახელი | მაქსიმუმ 20 შემოწმება |
შედარება ხაზოვან ძებნაზე 1,000,000 სახელზე: საშუალოდ 500,000 შემოწმება.
ორობითი ძებნა აჭრის სიას ნახევრად თითოეულ დროს. აჭრა ნახევრად განმეორებით მიაღწევს 1-მდე ძალიან სწრაფად — ამიტომ რჩება ასე სწრაფი.
იპოვეთ 'fig' დახარისხებული სიაში
აქ არის 8 სიტყვის დახარისხებული სია:
1. apple 2. banana 3. cherry 4. date 5. elderberry 6. fig 7. grape 8. honeydew
გსურთ იპოვოთ fig ორობითი ძებნის გამოყენებით.
მახსოვით: შემოწმება შუაგნაფი, იკითხეთ თქვენი სამიზნე მოდის ადრე თუ შემდეგ, შემდეგ გადააგდეთ სია ნახევრად.
მეზობლების განცვლა რიგში
ბუშტის დახარისხება: შედარება მეზობლები & განცვლა
ბუშტის დახარისხება რიგში ადის სიას ორი მეზობელი ელემენტის შედარებით ერთ დროს.
თუ ორი მეზობელი არის არასწორი რიგში — განცვალეთ ისინი.
განაგრძეთ სიის გამავლები სანამ არაფერი მოითხოვს განცვლას.
მაგალითი: რიგმდელი [5, 3, 8, 1]
წინ 1:
- შედარება 5 & 3. 5 > 3, ამიტომ განცვალეთ → [3, 5, 8, 1]
- შედარება 5 & 8. 5 < 8, განცვლის გარეშე → [3, 5, 8, 1]
- შედარება 8 & 1. 8 > 1, ამიტომ განცვალეთ → [3, 5, 1, 8]
წინ 2:
- შედარება 3 & 5. OK → [3, 5, 1, 8]
- შედარება 5 & 1. 5 > 1, განცვალეთ → [3, 1, 5, 8]
- შედარება 5 & 8. OK → [3, 1, 5, 8]
წინ 3:
- შედარება 3 & 1. 3 > 1, განცვალეთ → [1, 3, 5, 8]
- შედარება 3 & 5. OK. შედარება 5 & 8. OK.
შესრულებული! [1, 3, 5, 8] ✓
შენიშვნა: დიდი რიცხვი ბუშტოვანი სიის ბოლოს თითოეულ წინ. ასე მოჯდება ბუშტის დახარისხება მის სახელს.
ბუშტის დახარისხება მუშაობს. ის არ არის ყველაზე სწრაფი დიდი სიებისთვის, მაგრამ ის ადვილი გასაგებია — სრულყოფილი სწავლებისთვის.
რიგმდელი [4, 2, 7, 1] ბუშტის დახარისხებით
რიგმდელი ეს სია ბუშტის დახარისხებით: [4, 2, 7, 1]
ნაჩვენები სია თითოეული წინის შემდეგ. დაითვალეთ რამდენი წინი ხელმძღვანელი შესრულების ბოლოს.