რთულობის თითოეული კლასი მრუდს ხატავს
ხარჯის ნაკვეთი შეყვანის ზომის წინააღმდეგ
განათავსეთ შეყვანის ზომა N x-ღერძზე. განათავსეთ ხარჯი (ოპერაციები, დრო) y-ღერძზე. რთულობის თითოეული კლასი აწარმოებს მკაფიო მრუდს. თქვენ შეძლებთ ალგორითმის ზრდის მაჩვენებლის ამოცნობას მისი საქმის მრუდის ფორმიდან.
O(1) — ბრტელი ჰორიზონტალური ხაზი. ფუნქცია f(N) = 1. ქანობი არ არის. ხარჯი არასოდეს იცვლება, მიუხედავად N-ისა. ჰეშ-ცხრილის მოძებნა: იმ დროს, რომელი ცხრილი შეიცავს 10 ელემენტს თუ 10,000,000 ელემენტს, ერთი ჰეშ-გამოთვლა ხტება სწორ კოვჩეგში.
O(log N) — ღრმა ზემოთ მრუდი, ქანობი კლებადი. N = 1,000,000-ზე: ხარჯი ≈ 20 ოპერაცია. მრუდი მეკრთამედ მწეზე მცირე N-ზე, შემდეგ ჩამოიკეცება. N-ის თითოეული გაორმაგება ზუსტად ერთ ერთეულ ხარჯს ამატებს.
O(N) — დიაგონალური სწორი ხაზი. ქანობი = 1 (ასიმპტოტური აზრით). ხარჯი იზრდება N-ის იგივე სიჩქარით. თუ N სამჯერ იზრდება, ხარჯიც სამჯერ იზრდება.
O(N log N) — უფრო ციცაბო დიაგონალი მცირე ზემოთ მრუდით. ზეთ O(N)-დან მაგრამ ქვეთ O(N²)-დან. ლოგარითმული ფაქტორი ლინიარული ქანობს ნელი ზრდადი მულტიპლიკატორს ამატებს.
O(N²) — პარაბოლა ზემოთ გახსნილი. ქანობი იზრდება N-ის ზრდასთან. N = 10-ზე: ხარჯი = 100. N = 100-ზე: ხარჯი = 10,000. N = 1,000-ზე: ხარჯი = 1,000,000.
მზარდი უფსკელი
თანაფარდობა O(N²) / O(N) = N. უფსკელი პარაბოლასა და დიაგონალს შორის გაფართოვდება N-ის ზრდასთან. N = 10-ზე: 10× უფსკელი. N = 100-ზე: 100× უფსკელი. N = 1,000-ზე: 1,000× უფსკელი. N = 50,000-ზე: 50,000× უფსკელი. უფსკელი ყოველთვის N-ის ტოლია.
მასშტაბის უფსკელის გაანგარიშება
დიდი დამოკიდებულების გრაფი შეიცავს 50,000 პაკეტს (N = 50,000). ერთი ალგორითმი O(N) დროში ტრიალებს. მეორე O(N²)-ში. ამ N-ზე, თანაფარდობა O(N²)/O(N) = N = 50,000.
ხაზის სეგმენტის ორ ნაწილად გაყოფა
ორობითი ძებნა როგორც განმეორებული ნახევრება
N ელემენტის დახარისხებული მასივი ქმნის ხაზის სეგმენტს N სიგრძით. ორობითი ძებნა განმეორებით ორ ნაწილად ყოფს ამ სეგმენტს:
1. მიუთითეთ დარჩენილი სეგმენტის შუაწერტილზე.
2. თუ სამიზნე < შუაწერტილი: მარჯვენა ნახევარი გაქრება. გამეორება მარცხენა ნახევარზე.
3. თუ სამიზნე > შუაწერტილი: მარცხენა ნახევარი გაქრება. გამეორება მარჯვენა ნახევარზე.
4. თუ სამიზნე = შუაწერტილი: დასრულდა.
k ნახევრების შემდეგ, დარჩენილი სეგმენტი სიგრძით N / 2^k. ძებნა მთავრდება, როდესაც ეს სიგრძე ტოლი იყო 1:
N / 2^k = 1 → 2^k = N → k = log₂N
ასე რომ ორობითი ძებნა N ელემენტზე მოითხოვს მაქსიმუმ log₂N შედარებას.
ნახევრება & გაორმაგება: იგივე მრუდის ორი მხარე
ნახევრება და გაორმაგება გეომეტრიული ინვერსია. ექსპონენციალური მრუდი 2^k და ლოგარითმული მრუდი log₂N არის ერთმეორის ანარეკლი y = x ხაზის გასწვრივ.
განვიხილოთ ქაღალდის დასაკეცი: ფურცელი იწყება 0.1 მმ სისქით. თითოეული დაკეცვა გაორმაგებს სისქეს. 42 დაკეცვის შემდეგ: 0.1 მმ × 2^42 ≈ 439,804 კმ — მოიაკე აღემატება (384,400 კმ). ორობითი ძებნა ტრიალებს შებრუნებულად: დაიწყო N ელემენტით, თითოეული ნაბიჯი ნახევრებს ქვეყნის რაოდენობას, მიაღწიოს 1 ელემენტს log₂N ნაბიჯებში.
გეომეტრია: ორ ნაწილად გაყოფა არის თვითორმსიმილარული ოპერაცია. თითოეული ორ ნაწილად გაყოფა აწარმოებს ორ ნახევრებს, რომლებიც ოპტიკურად იდენტიკური სტრუქტურით არის მთელთან. რეკურსია და ლოგარითმები იზიარებენ ამ თვითორმსიმილარობას.
შედარებები & გაორმაგებები
დახარისხებული მასივი შეიცავს 1,048,576 ელემენტს. შენიშვნა: 1,048,576 = 2^20.
ჰეშ-ფუნქცია როგორც გეომეტრიული რუკა
ჰეშ-ფუნქცია როგორც ფუნქცია
ჰეშ-ცხრილი გამასხვევს გასაღებს კოვჩეგში ჰეშ-ფუნქციის გამოყენებით:
bucket = hash(key) mod table_size
ეს არის ფუნქცია მკაცრი მათემატიკური აზრით: ის გამასხვევს განსაზღვრის არეს (ყველა შესაძლო გასაღები) მნიშვნელობების დიაპაზონის (კოვჩეგების ინდექსები 0-დან table_size − 1-მდე). გეომეტრიული სურათი: გასაღებები ერთ სივრცეში ცხოვრობენ; კოვჩეგები სხვაში. ჰეშ-ფუნქცია პროექტირებს გასაღებებს კოვჩეგების ინდექსებში.
O(1) მოძებნა — პირდაპირი ხტომა, არ არის ძებნა. ჰეშ-ფუნქცია კოვჩეგის ინდექსს გამოთვლის მუდმივ დროში. ხტა პირდაპირ იმ კოვჩეგზე. არ არის გადაკვეთა, არ არის შედარების მარყუჟი.
დატვირთვის ფაქტორი. 0.75 დატვირთვის ფაქტორზე, 75% კოვჩეგი შეიცავს მინიმუმ ერთ ელემენტს. ~0.9-ზე მეტი, კოლიზიები იზრდება: ორი გასაღები ერთსა და იმავე კოვჩეგში ღეშავს, აყალიბებს ელემენტების ჯაჭვს იმ კოვჩეგში. მოძებნა ხანგრძლივ ჯაჭვში დეგრადირდება O(N)-მდე უარეს შემთხვევაში.
განაწილების ხარისხი როგორც გეომეტრია
კარგად განაწილებული ჰეშ-ფუნქცია ხსნის გასაღებებს თანაბრად ყველა კოვჩეგში. გეომეტრიულად: ფუნქციის დიაპაზონი ნაწილდება თავის კოდომენტზე რაც შეიძლება თანაბრად. თითოეული კოვჩეგი მიიღებს დაახლოებით N / table_size გასაღებებს.
ცუდი ჰეშ-ფუნქცია მოაგროვებს გასაღებებს რამდენიმე კოვჩეგში. გეომეტრიულად: ფუნქციის დიაპაზონი ეშვება კოდომენტის ქვესიმრავლემდე — უმეტესი გასაღებები ერთსა და იმავე რამდენიმე წერტილზე ღეშავს. დარჩენილი კოვჩეგი ცარი დგას.
კავშირი MOAD-0001-თან
სიის ჩანაცვლება კრებულით ამოჩნდება MOAD-0001 რადგან კრებული გამოიყენებს ჰეშ-ცხრილს შიგნით. O(N) სიის სკანი → O(1) ჰეშ-ცხრილის მოძებნა. გეომეტრიულად: ხაზოვანი გადაკვეთა თანმიმდევრობის გასწვრივ გადაკეთდება პირდაპირ პროექციებში ფუნქციის გამოყენებით. თანმიმდევრობა ქრება; ფუნქცია მას ჩაანაცვლებს.
ცუდად განაწილებული ჰეშის ანალიზი
ჰეშ-ცხრილი 1,000 კოვჩეგით და 900 ელემენტით (დატვირთვის ფაქტორი 0.9). ცუდი ჰეშ-ფუნქცია გარიგებას 500 იმ ელემენტს ერთსა და იმავე კოვჩეგში.