საუკეთესო, უარესი & საშუალო შემთხვევა
ალგორითმის გაზომვის სამი გზა
ყველა ალგორითმის ღირებულება დამოკიდებულია მის შეტანაზე. ორი შეტანა იმავე ზომის გაზე შეიძლება სრულიად განსხვავებული გაშვების დროები გამოიწვიოს. რთულობის ანალიზი იმ ვარიაციის სამი განსხვავებული პერსპექტივის ფორმალიზაციაა.
საუკეთესო შემთხვევა — Ω (Omega): შეტანა, რომელიც ალგორითმს ყველაზე სწრაფად დასრულებდე გარ. წერტილოვანი ძებნა N ელემენტის სიის ზე: Ω(1) — მიზანი პირველ პოზიციაზე მდებარეობს. ერთი შედარება, დასრულდა.
უარესი შემთხვევა — O (Big O): შეტანა, რომელიც ალგორითმს ყველაზე ნელა დასრულებდე გარ. წერტილოვანი ძებნა: O(N) — მიზანი სიის ბოლოს მდებარეობს, ან საერთოდ არ უჩნდება. თითოეული ელემენტი დამტკიცებას მოითხოვს.
საშუალო შემთხვევა — Θ (Theta): მოსალოდნელი ღირებულება ყველა შესაძლო შეტანაზე, თანაბარი განაწილების დაშვებით. წერტილოვანი ძებნა N პოზიციის თანაბარი ალბათობით: Θ(N/2) = Θ(N). მუდმივი 1/2 ქვეითდება, რადგან Theta გამოხატავს მჭიდრო ასიმპტოტურ ზრდას, არა ზუსტ კოეფიციენტებს.
რატომ უარესი შემთხვევა დომინირებს
სისტემებმა უარესი შემთხვევა უნდა დაამუშავოს. მონაცემთა ბაზის შეკითხვა, რომელიც საშუალოდ 10 ms, მაგრამ ზოგჯერ 60 წამს იკავებს, გამომწვევს მომხმარებელ-ხილვადი წარუმატებელი. ინჟინრები ისე იზომებს უარესი შემთხვევის საზღვრებისთვის, რომ წარმადობა რჩება საპროგნოზო, რაც შეტანა იყო არ. საშუალო შემთხვევის ანალიზი მნიშვნელოვანია ალბათურ გარემოში, მაგრამ უარესი შემთხვევის ანალიზი გარანტიებს იძლევა.
ორობითი ძებნის შემთხვევის ანალიზი
ორობითი ძებნა მხოლოდ დალაგებულ მასივებზე მუშაობს. თითოეულ ნაბიჯზე: შეადარე მიზანი შუამოდელის ელემენტს. თუ მიზანი ტოლია შუამოდელს, დააბრუნე. თუ მიზანი უფრო მცირეა, რეკურსივი მარცხნივ ნახევარზე. თუ უფრო დიდია, რეკურსივი მარჯვნივ ნახევარზე.
თითოეული შედარება აღმოფხვრის დარჩენილი კანდიდატების ნახევარს.
მეხსიერების ზრდა & დრო-სივრცის კომპრომისი
მეხსიერების დათვლა, არა ოპერაციების
დროის რთულობა ზომავს ოპერაციების რაოდენობას, რომელსაც ალგორითმი ასრულებს. სივრცის რთულობა ზომავს დამატებით მეხსიერებას, რომელიც ის განაწილებს მის შეტანის გარეშე. ორივე მნიშვნელოვანია წარმოებაში სისტემებში: სწრაფი ალგორითმი, რომელიც განაწილებს O(N²) მეხსიერებას, სერვერის მეხსიერება დასამთავრებელია.
O(1) სივრცე: მუდმივი დამატებითი მეხსიერება N აბსოლუტურ განურჩევლად. წაკითხვის ადგილი დალაგება (მაგ. ჩასმის დალაგება) ელემენტების გაცვლა ორიგინალ მასივში. იყენებს სახელურის სერვო ცვლადებს — O(1) მასივი რაც დიდი არ იყო.
O(N) სივრცე: მეხსიერება პროპორციული შეტანის ზომაზე. N-ელემენტი მასივის ასლის შექმნა მოითხოვს N ღრიობს. N სტრიქონების ჰეშ-მასივის შექმნა შესანახი სარეზერვო N ჩანაწერ.
O(N²) სივრცე: მეხსიერება პროპორციული N². N×N მიმდებარე მატრიცის შექმნა გრაფიკისთვის N წვეტებით მოითხოვს N² უჯრებს. N = 10,000 წვეტებით, რომ არის 10^8 ჩანაწერი — ასობით მეგაბაიტი მარტივი ლოგიკური ბადისთვის.
დრო-სივრცის კომპრომისი
ფундამენტური ნაბიჯი ალგორითმის დიზაინში: დროს სივრცის, ან სივრცის დროს სავაჭროდ.
ჰეშ-ცხრილი იყენებს O(N) დამატებით სივრცეს O(1) ძებნის მისაღწევად. ჰეშ-ცხრილის გარეშე, სიის სკანირება მიაღწევს O(N) ძებნას O(1) დამატებით სივრცეზე. ჰეშ-ცხრილი გამზიდის მეხსიერება სიჩქარე ყიდასთვის.
Memoization ინახავს წინა გამოთვლილ შედეგებს (O(N) ან მეტი სივრცე) გაიმეორებული რეკომპიუტაციის თავიდან ასაცილებლად. რეკურსიული ფიბონაჩი მემოაციის გარეშე ხელმისაწვდომელია O(2^N) დროში. Memoization: O(N) დროი O(N) სივრცეზე. სივრცის ინვესტიცია შემცირებს დროს მეწამულად.
ჰეშ-ლექსიკონი vs დალაგებული სია
შეადარე ორი სტრატეგია სიტყვის აღმოჩენის დათვლისთვის დოკუმენტში N სიტყვებით:
სტრატეგია A: ლექსიკონი (ჰეშ მაპა). ჩასმა თითოეული სიტყვა; მისი რაოდენობის ნაზრდი.
სტრატეგია B: შენახვა დალაგებული სია ხილული სიტყვებით; გამოიყენე ორობითი ძებნა წევრობის შემოწმების პირველი ჩასმამდე.
ამორტიზირებული ანალიზი: ღირებულების გადანაწილება
როდის შემთხვევითი ღირებულება არ გაუფუჯავს საშუალო წარმადობა
ზოგიერთი ოპერაციები აბსოლუტურად ძვირი კი არამედ ხელმისაწვდომელი საშუალოზე თანმიმდევრობის. ამორტიზირებული ანალიზი გამოითვლის საშუალო ღირებულება თითოეულ ოპერაციას მთელი თანმიმდევრობის — არა უარესი შემთხვევის ღირებულება ერთი ოპერაციის.
დინამიკური მასივი (Python სია, Java ArrayList): დაწყება სიმძლავრე 1. როდის სავსე, მედლავის სიმძლავრე. მედლავის ყველა ორიგინალი ელემენტი: O(N) მუშაობა მე ერთი მერე. მაგრამ მედლავი იშვიათი. დასრულების N მოჯამე მერე-შემდგომ, თვლიდან თვლამე სულ რამდენი ასლი ოპერაციები წარმოიქმნა?
მედლავი წარმოიქმნება სიმძლავრე 1, 2, 4, 8, ..., N/2. ასლი თვლა: 1 + 2 + 4 + ... + N/2. რომელიც არის გეომეტრიული სერია მოჯამე N − 1 სულ ასლი N ზე გარკვევილი მერე-შემდგომ. საშუალო ასლი თითოეული მერე-შემდგომ: (N − 1) / N < 1, რაც O(1) ამორტიზირებული თითოეული მერე-შემდგომ განკითხვა O(N) უარესი შემთხვევა თითოეული მედლავის.
რატომ ამორტიზირებული ანალიზი მნიშვნელოვანი
სისტემა, რომელიც ზოგჯერ პაუზა სიმძლავრე შეცვლა, ბალანსი, ან კომპაქტი სტრუქტურა შეიძლება ჩანდეს გაშინებული უარესი შემთხვევა ერთი ოპერაციები. ამორტიზირებული ანალიზი ვლინდება, რომელიც განცხადება მცდარი: იშვიათი ძვირი მოვლენა გადახდა ბევრი ხელმისაწვდომელი რომელი. ამორტიზირებული ღირებულება ჩავიდა თავიდან ზე-ინჟინერია: დამატებითი გართულებისთვის აბსოლუტურად O(N) ოპერაციის, რომელიც დაკლდა მხოლოდ O(1) ამორტიზირებული არის დაკარგული მუშაობა.
თეორია ღრმა: The unhamming ენტი ვრცელი რთულობის ანალიზი რეალ-მსოფლიო დეფექტი წარმოებაში პროგრამული. ხილვა აკოემი გაკვეთილი: ალგორითმი რთულობა & MOAD-0001: დალიის დეფექტი.
ჰეშ-ცხრილი ამორტიზირებული ჩასმა
ჰეშ-ცხრილი დაწყება ცარიელი და მედლავი სიმძლავრე, როდის დატვირთვის კოეფიციენტი აღემატება 0.75. 1,000 ელემენტის ჩასმა ხელმისაწვდომელი ზუსტი 10 მედლავი სიმძლავრე 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.