როგორ იზრდება ღირებულება

Big O ზომავს, როგორ იზრდება ღირებულება, როდესაც შეყვანა იზრდება. არა მუდმივი ფაქტორი — არამედ ტემპი. ორი ალგორითმი, რომლებიც N=100-ზე „რამდენიმე მილიწამში“ მუშაობენ, შეიძლება N=10,000-ზე 10,000-ჯერ განსხვავდებოდეს, თუ ერთი მუშაობს O(N) დროში, მეორე კი O(N²)-ში.

სირთულის ძირითადი კლასები

O(1) — მუდმივი. იგივე ღირებულება N-ის მიუხედავად. მაგალითები: ჰეშ-ცხრილის ძებნა გასაღებით, მასივის წვდომა ინდექსით, სტეკის push/pop. N-ის გაორმაგება არაფერს ცვლის.

O(log N) — ლოგარითმული. თითოეული ნაბიჯი ნახევრად ამცირებს დარჩენილ სამუშაოს. მაგალითები: ორობითი ძებნა დალაგებულ მასივში, BVH სივრცითი მოთხოვნა თამაშის ძრავაში, დაბალანსებული ორობითი ხის ოპერაციები. N=1,000,000-ზე: log₂(1,000,000) ≈ 20 ნაბიჯი.

O(N) — წრფივი. ღირებულება იზრდება შეყვანის მიხედვით. მაგალითები: სიის წრფივი სკანირება, ფაილის წაკითხვა, კოლექციაში ელემენტების დათვლა. N=10,000-ზე: 10,000 ოპერაცია.

O(N log N) — წრფივ-ლოგარითმული. თითქმის წრფივი, ოდნავ უარესი. მაგალითები: შერწყმის სორტირება, ეფექტური უმოკლესი გზის ალგორითმები (Dijkstra heap-ით). N=10,000-ზე: ~133,000 ოპერაცია.

O(N²) — კვადრატული. ღირებულება აფეთქდება. მაგალითები: list.contains() გამოძახებული იმავე სიის მარყუჟში, ბუშტის სორტირება, ნაივი ყველა-წყვილის შედარება. N=1,000-ზე: 1,000,000 ოპერაცია. N=10,000-ზე: 100,000,000 ოპერაცია.

O(2^N) — ექსპონენციალური. გამოუსადეგარია ნებისმიერ მნიშვნელოვან მასშტაბზე. მაგალითები: ბრუტალური კომბინატორიკა, ყველა ქვესიმრავლის პოვნა. N=30-ზე: 1,000,000,000-ზე მეტი ოპერაცია.

მასშტაბი, რომელიც მას ხილულს ხდის

N=10 შედარება:
O(N):   10
O(N²):  100
თანაფარდობა:  10x

N=1,000 შედარება:
O(N):   1,000
O(N²):  1,000,000
თანაფარდობა:  1,000x

N=10,000 შედარება:
O(N):   10,000
O(N²):  100,000,000
ratio:  10,000x

როდესაც N=10, განსხვავება თითქმის არ ჩანს. როდესაც N=10,000, O(N²) ალგორითმი 10,000-ჯერ უფრო ნელია. სწორედ ამიტომ დარჩა MOAD-0001 უხილავი ათწლეულების განმავლობაში: 1993 წელს მის მიერ გამოყენებულ გრაფებში 50 კვანძი იყო. 2020 წლისთვის იგივე კოდი უკვე 50,000 კვანძიან დამოკიდებულების გრაფებზე მუშაობდა.

სამი ოპერაციის კლასიფიკაცია

გამოიყენეთ სირთულის კლასები კონკრეტულ ოპერაციებზე. თითოეული ოპერაციისთვის მთავარი კითხვაა: რამდენი ოპერაციაა საჭირო N-ის ზრდასთან ერთად?

სწორი კოდი, არასწორი ზრდის მრუდი

სწორი კოდი, რომელიც მუშაობს O(N²) დროში, იძლევა იგივე შედეგს, რასაც O(N) კოდი. ტესტები გადის. გამომავალი ემთხვევა. გამონაკლისი არ ჩნდება. დეფექტი იმალება ზრდის მრუდში.

ეს თვისება O(N²) დეფექტებს აქცევს დანალექად: ისინი ქვავდებიან მომუშავე კოდში და მხოლოდ მაშინ ხდებიან ხილულები, როცა N გადასცდება გარკვეულ ზღვარს. კოდი არ შეცვლილა. შეიცვალა სამყარო მის გარშემო.

MOAD-0001: დანალექი დეფექტი

ყველაზე გავრცელებული შემთხვევა: visited = [] გრაფის ტრავერსიის ციკლში.

visited = []
for node in graph:
if node not in visited:  # O(N) სკანირება ყოველ გამოძახებაზე
visited.append(node)
process(node)

თითოეული not in visited გამოძახება სკანირებს 0-დან len(visited)-1 ელემენტამდე. N გამოძახება × საშუალოდ N/2 სკანირებული ელემენტი = O(N²) საერთო. გამოსწორება: ერთი ხაზი.

visited = set()  # O(1) წევრობის შემოწმება
for node in graph:
if node not in visited:  # O(1) ჰეშის ძებნა
visited.add(node)
process(node)

იგივე ქცევა. იგივე გამომავალი. იგივე ტესტები გადის. ზრდის სიჩქარე იცვლება O(N²)-დან O(N)-ზე. N=1,000-ზე: 1,000× უფრო სწრაფი. N=10,000-ზე: 10,000× უფრო სწრაფი.

რატომ დათესა ჰამინგის ეპოქამ ეს

ადრეულ Java-სა და C-ში ArrayList (დინამიური მასივი) იყო ნაგულისხმევი თანმიმდევრული კონტეინერი. სეტები არსებობდა, მაგრამ არ იყო იდიომატური — დეველოპერები იყენებდნენ იმას, რაც ნაცნობი იყო. 1993 წლის გრაფის ტრავერსი N=50-ზე მუშაობდა მიკროწამებში visited = []-ით. ეს კოდი შევიდა ვერსიის კონტროლში, გადაკოპირდა, შეფუთეს ბიბლიოთეკებში, გავრცელდა პაკეტ მენეჯერებში. 2020 წლისთვის იგივე შაბლონი მუშაობდა დამოკიდებულებების გრაფებზე 50,000 კვანძით.

კოდი სწორი იყო 1993 წელს. ის გახდა ძვირი, როდესაც სამყარო მის გარშემო შეიცვალა. ჰამინგის ეპოქამ დათესა ამ ტიპის დეფექტი, რადგან არასოდეს დაასახელა ზრდის სიჩქარის კითხვა.

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

გამოიყენეთ დიაგნოზი: იპოვეთ O(N²) შაბლონი, განსაზღვრეთ გამოსწორება.

რა სახელის ცვლილებები [BLOCK_TYPE SECTION/STEP]

სანამ Big O-ს სახელი ჰქონდა, პროგრამისტები ამჩნევდნენ „ეს ნელა მუშაობს“. ისინი აკეთებდნენ პროფილირებას. გადაწერდნენ კოდს. მაგრამ ვერ ასწავლიდნენ შაბლონს — მხოლოდ მაგალითებს უჩვენებდნენ. სახელის გარეშე შაბლონი ვერ გავრცელდება. [BLOCK_TYPE SECTION/STEP]

მას შემდეგ, რაც Big O-ს სახელი მიენიჭა, უფროს ინჟინერს შეეძლო თქვა „ეს არის O(N²), შეცვალეთ set-ით“ და უმცროს ინჟინერს შეეძლო გაეგო, გამოეყენებინა და თავის მხრივ ესწავლებინა შაბლონი. სახელმა შაბლონი გახადა ცოდნის გადასაცემი ერთეული. [BLOCK_TYPE SECTION/STEP]

ჰამინგმა იცოდა ეს დინამიკა სხვა დომენებში. მან აღწერა, როგორ მისცა სახელი „spaghetti code“-ს 1960-იან წლებში საზოგადოებას საშუალება ამოეცნო, განეხილა და საბოლოოდ აღმოფხვრა დეფექტების კლასი, რომელიც ყველას განუცდია, მაგრამ არავის დაუსახელებია. იგივე მექანიზმი ვრცელდება სირთულის კლასებზე. [BLOCK_TYPE SECTION/STEP]

Unhamming ამატებს ლექსიკას, რომელიც ჰამინგმა გამოტოვა: O(1), O(log N), O(N), O(N log N), O(N²), O(2^N). ეს სახელები საშუალებას გაძლევთ დაინახოთ ზრდის მრუდი კოდში, რომელსაც კითხულობთ, წინასწარ განსაზღვროთ შესრულება მასშტაბზე და ზუსტად გადმოსცეთ გამოსწორებები. ისინი აკმაყოფილებენ ჰამინგის საკუთარ ტესტს ფუნდამენტალისთვის: გამძლე და გენერირებს დარგის უმეტეს ნაწილს.

რიცხვთა თეორიიდან კომპიუტერულ მეცნიერებამდე

Big O აღნიშვნა არ წარმოიშვა კომპიუტერულ მეცნიერებაში. იგი წარმოიშვა წმინდა მათემატიკაში — კერძოდ, რიცხვთა თეორიაში — 74 წლით ადრე, სანამ დონალდ კნუთი მას ალგორითმებისთვის მოარგებდა.

პაულ ბახმანი, 1894

პაულ ბახმანმა, გერმანელმა მათემატიკოსმა, შემოიღო O აღნიშვნა თავის 1894 წლის წიგნში Die Analytische Zahlentheorie (ანალიტიკური რიცხვთა თეორია). მას სჭირდებოდა კომპაქტური გზა, რათა გამოეხატა, რომ ერთი სიდიდე მეორეზე არა უფრო სწრაფად იზრდება, მუდმივი ფაქტორის ფარგლებში. ჩანაწერი „f(n) = O(g(n))“ ნიშნავდა: f იზრდება მაქსიმუმ იმავე სიჩქარით, როგორც g. ამან რიცხვთა თეორეტიკოსებს საშუალება მისცა, მიახლოებების შეცდომის წევრებზე მსჯელობა მუდმივების ზუსტი თვალყურის დევნების გარეშე.

ბახმანი არ ფიქრობდა ციკლებზე, მონაცემთა სტრუქტურებზე ან შესრულების დროზე. იგი ფიქრობდა მარტივ რიცხვთა განაწილებაზე — კერძოდ, მარტივ რიცხვთა თეორემის შეცდომის წევრებზე.

ედმუნდ ლანდაუ, 1909

ედმუნდ ლანდაუ, კიდევ ერთი გერმანელი მათემატიკოსი, პოპულარიზაცია გაუწია აღნიშვნას თავის 1909 წლის წიგნში Handbuch der Lehre von der Verteilung der Primzahlen (მარტივ რიცხვთა განაწილების შესახებ სახელმძღვანელო). ლანდაუმ ასევე შემოიღო დაკავშირებული აღნიშვნა o (პატარა-o) და იმდენად ფართოდ იყენებდა ასიმპტოტური სიმბოლოების ოჯახს, რომ მთელი ოჯახი ცნობილი გახდა როგორც Bachmann-Landau აღნიშვნა ან უბრალოდ Landau აღნიშვნა.

ექვსი ათწლეულის განმავლობაში O აღნიშვნა მთლიანად მათემატიკაში ცხოვრობდა. არც ერთი პროგრამისტი არ ფიქრობდა მასზე.

დონალდ კნუთი, 1968 & 1976

დონალდ კნუთმა გადაიტანა ეს აღნიშვნა კომპიუტერულ მეცნიერებაში. წიგნში კომპიუტერული პროგრამირების ხელოვნება (ტ. 1, 1968) კნუთმა გამოიყენა O აღნიშვნა ალგორითმების შესრულების დროის აღსაწერად — ბახმანის ინსტრუმენტის პირდაპირი გადატანა ახალ დომენში. ის იყო პირველი, ვინც სისტემატურად გამოიყენა იგი ალგორითმების ანალიზში.

1976 წელს კნუთმა გამოაქვეყნა მოკლე სტატია SIGACT News-ში სათაურით „Big Omicron and Big Omega and Big Theta“. მან შემოიტანა Omega (Ω) ქვედა ზღვრებისთვის და Theta (Θ) მკაცრი ზღვრებისთვის, რითაც დაასრულა სამსიმბოლოიანი ლექსიკა, რომელსაც დღეს კომპიუტერული მეცნიერება იყენებს. მან ასევე მოითხოვა ამ სიმბოლოების სტანდარტიზაცია მთელს დარგში — მიზანმიმართული სტანდარტიზაციის აქტი, რომელმაც დააჩქარა მათი გავრცელება.

1980-იანი წლების დასაწყისისთვის Big O ყველა ალგორითმების სახელმძღვანელოში გამოჩნდა. 1990-იანი წლებისთვის ის გახდა ინტერვიუს სტანდარტული ლექსიკა.

74-წლიანი მოგზაურობა

1894 — ბახმანი შემოაქვს O რიცხვთა თეორიაში
1909 — ლანდაუ პოპულარიზაციას უწევს O-ს, o-ს და სრულ აღნიშვნათა ოჯახს
1953 — Hamming იწყებს კვლევას Bell Labs-ში (არასოდეს სწავლობს Big O-ს როგორც CS ინსტრუმენტს)
1968 — Knuth იყენებს O-ს ალგორითმების ანალიზისთვის TAOCP ტომი 1-ში
1976 — Knuth ამატებს Omega-ს და Theta-ს; ამტკიცებს სტანდარტიზაციისთვის
1980-იანები — Big O შედის ყველა CS სასწავლო პროგრამაში
1993 — MOAD-0001 ნალექის ფენა ყალიბდება წარმოების კოდში
1995 — Hamming ასწავლის თავისი კურსის საბოლოო ვერსიას; არასოდეს მოიცავს Big O-ს
2026 — MOAD-0001 აღმოჩენილია 1,000+ ღია წყაროს პროექტში

ბახმანის ინსტრუმენტი 74 წელი გაატარა წმინდა მათემატიკაში — ხილული ყველა მათემატიკოსისთვის, მაგრამ უხილავი ყველა პროგრამისტისთვის. კნუთმა დაინახა მისი გადანერგვის შესაძლებლობა. ჰამინგი — იმავე ეპოქაში მომუშავე და იმავე კომპიუტერულ საზოგადოებასთან თანამშრომლობით — არასოდეს ჩართო ეს თავის კურსში.

რატომ იყო მნიშვნელოვანი კნუთის სტანდარტიზაცია

კნუთის 1976 წლის სტატიამ გააკეთა რაღაც მეტი, ვიდრე უბრალოდ შემოიტანა Omega და Theta. მან დაამტკიცა, რომ სფეროს სჭირდებოდა თანმიმდევრული აღნიშვნა და რომ არათანმიმდევრული აღნიშვნა აქტიურად აზიანებდა პროცესს. სხვადასხვა სახელმძღვანელო იყენებდა O-ს სხვადასხვა მნიშვნელობით — ზოგჯერ როგორც ზედა ზღვარს, ზოგჯერ როგორც მიახლოებას, ზოგჯერ კი არ აზუსტებდა, მნიშვნელოვანია თუ არა მუდმივები. კნუთმა ეს გაასუფთავა.

ეს არის ჰამინგის შაბლონების დასახელების დინამიკა, გამოყენებული თავად აღნიშვნის მიმართ. სანამ კნუთი სტანდარტიზებდა სიმბოლოებს, ინჟინრებს არ შეეძლოთ სირთულის შესახებ მტკიცებების ზუსტად გადაცემა სახელმძღვანელოებს, სტატიებსა და გუნდებს შორის. სტანდარტიზაციის შემდეგ „ეს მუშაობს O(N log N)-ში“ ერთადერთ მნიშვნელობას ატარებდა, ვინც არ უნდა ეთქვა.

კნუთმა ასევე შემოიტანა არაფორმალური თარგმანი: „O(f(n)) ნიშნავს, რომ შესრულების დრო არის მაქსიმუმ მუდმივი ჯერ f(n), ყველა საკმარისად დიდი n-ისთვის.“ ეს ინტერპრეტაცია — ზედა ზღვარი, მუდმივი ფაქტორის ფარგლებში, დიდი შეყვანისთვის — გახდა სტანდარტული ინტუიცია, რომელსაც ყველა პროგრამისტი სწავლობს.