Big-O აღწერს, თუ როგორ იზრდება ალგორითმის სამუშაო დრო ან მეხსიერება, როდესაც შეყვანის ზომა n იზრდება. ის ловит უარეს შემთხვევაში ასიმპტოტური ქცევა, უგულელყოფს მუდმივები და დაბალი ხარისხის წევრები.
ჩვენ ვაფასებთ ზრდის სიჩქარეს, ეტაპების ზუსტი რაოდენობას არა. O(2n + 5) უბრალოდ O(n) არის, რადგან როდესაც n დიდი ხდება, მუდმივები და უფრო მცირე წევრები აღარ მნიშვნელოვანია.
| Big-O | სახელი | მაგალითი |
|---|
| O(1) | მუდმივი | მასივის ინდექსზე წვდომა |
| O(log n) | ლოგარითმული | ბინარული ძებნა |
| O(n) | ხაზოვანი | სიის სკანირება |
| O(n log n) | ხაზოვან-ლოგარითმული | შერწყმის დალაგება |
| O(n²) | კვადრატული | ჩასმული მარყუჟები |
| O(2ⁿ) | ექსპონენციალური | ნაივური ქვესიმრავლეები |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
Big-O ხავს მუდმივები: O(n) ალგორითმი უდიდესი მუდმივით შეიძლება დაკარგოს O(n log n)-ის წინააღმდეგ მცირე შეყვანებზე. აგრეთვე თვალი ადევნეთ სივრცე სირთულეს, არა მხოლოდ დროს.
Big-O საშუალებას გიძლევთ შეადაროთ ალგორითმები მათი გაშვების ან აპარატის შესახებ ფიქრის გარეშე.
ეს პროგნოზირება აკეთებს რომელი გადაწყვეტილებები ტარდება, როდესაც შეყვანა ასეულებიდან მილიონებზე იზრდება — განსხვავება თვისების მათ შორის, რომელიც სკალირდება და ის, რომელიც დროთ აღნიშვნის გარეშე.
ეს არის ვოკაბულარი, რომელსაც ყველა ინჟინერი იყენებს დამუშავების შესახებ მსჯელობისთვის.