კოდის სტრუქტურა ავლენს სირთულე

Big O-ს დადგენა კოდიდან

Big O იმალება თქვენი კოდის ფორმაში. ოთხი შაბლონი ფარავს უმეტეს შემთხვევებს:

ერთი მარყუჟი N ელემენტით: O(N)

# O(N): ერთი გავლა სიის
for item in list_of_n_items:
    process(item)

წყობილი მარყუჟი, თითოეული N ელემენტით: O(N²)

# O(N²): თითოეული ელემენტი დაწყვილებული ყველა სხვა ელემენტთან
for item_a in list_of_n_items:
    for item_b in list_of_n_items:
        compare(item_a, item_b)

მუდმივი დრო ძებნა: O(1)

მასივის ინდექსის წვდომა, ჰეშ-ტესელის ძებნა — ერთი ნაბიჯი მიუხედავად ზომისა.

დაყოფა-დაკავება (პრობლემის ნახევრად ჩამოჭრა ყოველ ნაბიჯზე): O(log N)

ორობითი ძებნა: თითოეული ფიქსაცია ნახევარდება დარჩენილი ელემენტები.

---

ფარული O(N²): სია მარყუჟის შიგნით

# ეს ჰგავს O(N) მაგრამ რეალურად O(N²)
visited = []
for item in list_of_n_items:
    if item not in visited:   # ტარდება ყველა visited: O(N)
        visited.append(item)  # მთელი მარყუჟი: O(N²)

if item not in visited სტრიქონი ტარდება visited-ის ყველა ელემენტი თითოეულ გამეორებაზე. სიის სკანი დაიჯდა O(N). მარყუჟი, რომელიც ჯერ N აკრეფს, თითოეული O(N) სამუშაო: O(N) × O(N) = O(N²).

ეს შაბლონი ჩნდება 1,000+ ღია-წყაროს პროექტებში. გასწორება იღებს ერთ სიმბოლოს: შეცვალეთ visited = [] visited = set()-ით. კომპლექტის გაწევრობის ტესტირება იჯდა O(1), არა O(N). ერთი ცვლილება. იგივე შედეგი. 1,000× სწრაფი N=1,000-ზე.

კლასიფიცირება & ამ კოდის გასწორება

წაიკითხეთ ეს კოდი:

result = []
for name in student_names:
    if name not in result:
        result.append(name)

თეორია შეხვდა პრაქტიკას

Big O ველური ხმელეთის

Big O არ არის მხოლოდ თეორია. იგი ტყვიფს პროგრამებს, რომლებიც მთავრდება წამში, პროგრამებისგან, რომლებიც 17 წუთი აღებს — ზუსტად იმავე ამოცანაზე.

რეალური მაგალითი: დამოკიდებულების წრის გამოვლენა ბიზნეს სისტემაში.

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

O(N²) წრის-გამოვლენის ალგორითმი მშვენივრად მუშაობს N=100 პაკეტზე. N=50,000 პაკეტზე (ნამდვილი პროექტი): ეს იღებს 17 წუთი. O(N) გასწორება: 10 წამი.

ეს ზუსტი დეფექტი არსებობს GHC-ში (Haskell კომპილატორი), pip-ში (Python პაკეტის მმართველი), Maven-ში (Java ბიზნეს სისტემა), Cargo-ში (Rust პაკეტის მმართველი), & 1,000+ სხვა პროექტებში.

არა, რადგან მათი ავტორი უიღბლო იყო. visited = [] დაწერილი იყო, როდესაც N მცირე იყო. კოდი კალციფიცირდა. N გაიზარდა. ვერავინ შენიშნა, სანამ ბიზნეს სისტემა ნახევარი საათი აიღო.

Big O არის ლექსიკონი, რომელიც დაეხმარება თქვენს რა მოხდა — & გასწორება.

---

სიღრმეში დაიტანო? ჩვენი unhamming კურსი კვამლი სრულ თავს Big O-ზე, MOAD-0001 (ნამდვილი O(N²) დეფექტი, რომელიც 1,000+ ღიაწყარო პროექტებში გვხვდება), & რატომ ნაწილის დამო თქვენ აღმოაჩენთ მას ყველგან. იხილეთ დაკარგული თავი: ალგორითმული სირთულე.

ვინმე ბიზნეს დროი

ბიზნეს სისტემა იყენებს O(N²) წრის-გამოვლენა.

გაზომილი ბიზნეს დრო:

- N=100 პაკეტი: 0.01 წამი

- N=1,000 პაკეტი: 1 წამი

O(N²)-ისთვის: დრო მასშტაბირებულია (N_new / N_old)².

O(N)-ისთვის: დრო მასშტაბირებულია (N_new / N_old).