სირთულე და ზრდის ტემპი

ორი პროგრამა შეიძლება ორივე სწორი იყოს, მაგრამ ერთი თვალის დახამხამებაში პასუხობს, მეორე კი მომავალ კვირამდე მუშაობს. Big-O გეუბნება, რომელია რომელი, ჯერ კიდევ კოდის დაწერამდე.

დამწყები⏱ 12 წთ

←ეყრდნობა

ეს საწყისი წერტილია: წინა თემა არ გჭირდება.

გზას უხსნის→

0რეკურსია და გამოძახებათა სტეკირეკურსიის ხეში გამოძახებების დათვლით ვაფასებთ რეკურსიული ფუნქციის სირთულეს.1მასივები და დინამიური მასივებიpush_back-ის საშუალო O(1) არის Big-O შეფასება ბევრ ოპერაციაზე ერთად.1ჰეშ-ცხრილები: set და mapსაშუალოდ O(1) და უარეს შემთხვევაში O(n): სწორედ ამ განსხვავებას გვასწავლის Big-O.1პრეფიქსული ჯამები, ორი მაჩვენებელი, მოცურავი ფანჯარაორივე ხერხი O(n²) ჩადგმულ ციკლებს ერთ O(n) გავლად აქცევს.2მარტივი სორტირებებიორ ჩადგმულ ციკლში შედარებების დათვლა აჩვენებს, რატომ არის ეს სორტირებები O(n²).2ორობითი ძებნა და ძებნა პასუხზეშუალედის განახევრება ყოველ ბიჯზე სწორედ ისაა, საიდანაც O(log n) მოდის.3მონოტონური სტეკითითო ელემენტი ერთხელ შედის და ერთხელ გამოდის, ამიტომ შიდა ციკლის მიუხედავად ჯამში O(n)-ია.4ქვესიმრავლეებისა და გადანაცვლებების გენერაცია2ⁿ ქვესიმრავლე და n! გადანაცვლება აჩვენებს, რა სწრაფად ფეთქდება ექსპონენციალური ზრდა.9უსგ და ერატოსთენეს საცერიევკლიდეს O(log n) და საცრის O(n log log n) ზრდის ტემპებია, რომლებიც უნდა იცნო.11გულუბრყვილო შაბლონის ძებნაშედარებების დათვლა O(n·m)-ს იძლევა და აჩვენებს, სად იკარგება შრომა.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01დაითვალე ბიჯები და არა წამები

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

ამიტომ ღირებულებას აღვწერთ შემავალი მონაცემების ზომის (n-ის) ფუნქციით. ერთი ციკლი მასივზე თითო ელემენტს ერთხელ ეხება: დაახლოებით n ბიჯი. ციკლი ციკლში ყველა წყვილს ეხება: დაახლოებით n × n ბიჯი.

n = 6-ისთვის ეს 6 და 36-ია. n = 100 000-ისთვის კი ასი ათასი და ათი მილიარდი. პირველი მყისიერად მთავრდება, მეორეს ბევრი წამი სჭირდება. კოდის ფორმა გეუბნება ღირებულების ფორმას.

02ზრდის ტემპების კიბე

რამდენიმე ფუნქცია თითქმის ყველა ალგორითმს ფარავს, რასაც შეხვდები, ყველაზე იაფიდან ყველაზე ძვირამდე:

O(1): მუდმივი, მაგ. a[i]-ის წაკითხვა
O(log n): ყოველ ბიჯზე ამოცანა ნახევრდება, მაგ. ორობითი ძებნა
O(n): მონაცემებზე ერთი გავლა
O(n log n): კარგი სორტირების ალგორითმები
O(n²): ყველა წყვილი, ჩადგმული ციკლები
O(2ⁿ): ყველა ქვესიმრავლე, სრული გადარჩევა

პატარა შემავალ მონაცემებზე ისინი ერთმანეთს ჰგვანან. n-ის ზრდასთან ერთად კი ყოველი საფეხური ქვედას შორს ტოვებს: 2ⁿ გრაფიკიდან გაფრინდება, log n კი თითქმის არ იძვრის.

n 1-დან 16-მდე; მრუდები წყდება, სადაც გრაფიკს სცდებიან.

03Big-O-ს ორი წესი

Big-O აღწერს ზრდას დიდი n-ისთვის, ამიტომ ორი გამარტივება დაშვებულია:

დატოვე მხოლოდ დომინანტი წევრი. 3n² + 5n + 9-ში n = 1000-ზე n²-ის წილი სამი მილიონია, დანარჩენი კი დაახლოებით ხუთი ათასი. მცირე წევრებს მნიშვნელობა ეკარგებათ.
უგულებელყავი მუდმივი მამრავლები. 3n² და n² ერთნაირად იზრდება: n-ს გააორმაგებ და ორივე ოთხჯერ გაიზრდება. ამიტომ 3n² + 5n + 9 უბრალოდ O(n²)-ია.

კოდის წაკითხვის წესები: მიმდევრობითი ბლოკები იკრიბება (იღებ უდიდესს), ჩადგმული ციკლები მრავლდება, ხოლო ციკლი, რომელიც ყოველ ჯერზე შუალედს ანახევრებს, O(log n)-ია. მეხსიერებაც ასევე იზომება: n ზომის დამატებითი მასივი O(n) მეხსიერებაა.

04შეზღუდვებიდან ალგორითმამდე

ჩვეულებრივი კომპიუტერი წამში დაახლოებით 10⁸ მარტივ ბიჯს ასრულებს. ეს ამოცანის პირობაში მოცემულ შეზღუდვებს შეუთავსე და სანამ დაიწყებ, მიხვდები, რა სირთულეს ელიან შენგან:

n ≤ 20: ქვესიმრავლეების ექსპონენციალური გადარჩევა გაივლის
n ≤ 5000: O(n²) გაივლის
n ≤ 10⁶: საჭიროა O(n log n) ან O(n)

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

მიახლოებითი ზღვრები დაახლოებით ერთი წამის მუშაობისთვის.

ფასი ერთი შეხედვით

a[i]-ის წაკითხვაO(1)

ყოველ ბიჯზე განახევრებაO(log n)

ერთი გავლაO(n)

კარგი სორტირებაO(n log n)

ყველა წყვილიO(n²)

ყველა ქვესიმრავლეO(2ⁿ)

დაიმახსოვრე

ღირებულება გაზომე ელემენტარული ბიჯების რაოდენობით, როგორც შემავალი მონაცემების ზომის (n-ის) ფუნქცია.
Big-O ინახავს მხოლოდ დომინანტ წევრს და აგდებს მუდმივებს, ამიტომ 3n² + 5n + 9 არის O(n²).
წამში დაახლოებით 10⁸ ბიჯის გათვალისწინებით, შეზღუდვები გეუბნება, რა სირთულე გჭირდება.

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: უყურე ბოლო სვეტს: n = 16-ისთვის 2ⁿ ყველას უსწრებს. სცადე შენი n-ები, მაგ. 10 20 30 40.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

ზრდის ტემპების შეჯიბრი

	n	log₂n	n·log₂n	n²	2ⁿ

Big-O აღწერს, როგორ იზრდება ალგორითმის ღირებულება შემავალი მონაცემების n-ის ზრდასთან ერთად. ვუყუროთ ხუთი ფუნქციის შეჯიბრს, სანამ n ორმაგდება.

ფსევდოკოდი

 1 // how does work grow with input size n? 2 compare  log n  <  n log n  <  n²  <  2ⁿ 3 O(f): ignore constants, keep the dominant term 4 // every lecture ends with an "ასიმპტოტიკა" slide

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

ფუნქციაში ციკლი i-ზე 0-დან n−1-მდე, მის შიგნით კი ციკლი j-ზე 0-დან 9-მდე. რა არის სირთულე?

№2

პირობაში წერია n ≤ 200 000. რომელი მიდგომა გაივლის სავარაუდოდ ერთ წამში?

№3

O(n²) პროგრამას n = 10 000-ზე 1 წამი სჭირდება. დაახლოებით რამდენი დასჭირდება n = 20 000-ზე?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

CSESWeird Algorithm დამწყები↗CSESMissing Number დამწყები↗LeetCodeContains Duplicate დამწყები↗CSESTwo Knights საშუალო↗