ალგორითმები

პროგრამირებაში ალგორითმი არის ინსტრუქციების თანმიმდევრობა, რომლის მეშვეობითაც ხდება პრობლემის გადაჭრა, რეალურ ცხოვრებაში ალგორითმი თქვენი ყოველ დღიური ცხოვრებაა, მაგალითად დგებით დილით, სხვამთ ყავას, მიდიხართ სამსახურში, ბრუნდებით სამსახურიდან, ეს ოთხი ოპერაცია ქმნის თქვენ დღეს, ზუსტად იგივე ლოგიკით იქმნება პროგრამაც, კომპიუტერულ მეცნიერებაში ალგორითმის ფუნქციონირება (დილა) იწყება მომხმარებლისგან, რომლისგანაც იღებს მოთხოვნას, კომპლექსურად დაწერილი კოდი ამუშავებს მოთხოვნას (სვამს ყავას), უბრუნებს შედეგს მომხმარებელს(მუშაობას) და ელოდება შემდეგ მითითებებს(ბრუნდება სახლში). ალგორითმების კარგად ცოდნა თქვენ საშუალებას მოგცემთ დაწეროთ მაღალი ხარისხის კოდი, რომელიც იქნება მოთხოვნადი ყველა სფეროში. (პროგრამისტები ყველაზე ხშირად რასაც არჩევენ ერთმანეთში ეს კოდის ალგორითმია) წარმოიდგინეთ რამოდენიმე მაგალითი, როგორ ფიქრობთ, როგორ ახერხებს google.com ან Facebook.com მაღალი ხარისხის ვიდეო ტრანსლაციას 0 წამში? მათ აქვთ შემუშავებული ვიდეო/აუდიო შეკუმნშვის ალგორითმი, რომელიც უზარმაზარ იმფორმაციას კუმშავს(ზიპავს) და აბრუნებს შედეგს, მეორე მაგალითი, როგორ ახერხებს google.com-ის საძიებო სისტემა 0 წამში დაგიბრუნოთ მილიონობით რეზულტატი? დაახლოებით იგივე ალგორითმით, რომელსაც ვიდეო ტრანსლაციის დროს იყენებს, აქვთ მონაცემთა ბაზა საიტების სადაც ძიება იწყება თქვენ მიერ შეყვანილ საკვანძო სიტყვაზე დაყრდნობით, დაყავი და იბანოტეს პრინციპით, ამუშავებს ტრილიარდობით მონაცემს სულ რამოდენიმე კოდური ველით. ეს ყველაფერი პროგრამული ლექსიკით რომ ვთქვათ, ალგორითმი არის პროგრამისტების ყოველ-დღიური ცხოვრება, სადაც თქვენ ცდილობთ უთხრათ კომპიუტერს თუ როგორ, რა გზით და რომელი ნაბიჯებით გადაჭრას პრობლემა. 

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

მაშ ასე, უკვე ვიცით რომ ალგორითმი არის პრობლემის თანმიმდევრულად გადაჭრის უნარი. მაგრამ პრობლემის გადაჭრა შედეგია? შეიძლება ყოველ-დღიურ ცხოვრებაში პრობლემის გადაჭრის უნარი შედეგი იყოს მაგრამ არა პროგრამირებაში, პროგრამირებაში თუ კოდს უდგებით ამ კუთხით მაშინ თქვენ კოდს ერთი კილო ბანანის ფასიც არ ექნება, სხვა ენით პროგრამირებაში პრობლემის გადაჭრით დაკმაყოფილება ნიშნავს ოროსნობას. პრობლემა გადავჭერი = ოროსანს.

თუ პრობლემის გადაჭრის უნარი მხოლოდ პირველი საფეხურია(დილა) მაშინ რა არის შემდეგი? რა გააუმჯობესებს კოდს?

კოდს დრო აუმჯობესებს და დიდი ინფორმაციის დამუშავების უნარი დროსთან მიმართებაში, რაც უფრო სწრაფად და გამართულად მუშაობს თქვენი კოდი მით უფრო მოთხოვნადია იგი. უყურეთ ამ ყველაფერს როგორც მარკეტინგულ სვლას. წარმოიდგინეთ google.com ძიების შედეგს 2 წამში რო აბრუნებდეს ეყოლებოდა 3 მილიარდი მომხმარებელი? თქვენ მომხმარებელი ხართ google.com-ის იმიტომ რო იცით ის 0 წამში მუშაობს, მაგრამ მისი საძიებო სისტემა რამოდენიმე წამი რო იყოს არ დაიწყებთ ალტერნატიული გვერდის ძიებას? დაიწყებთ დამიჯერეთ. კომპიუტერთან 1 წამი დიდი დროა. 

ამ ყველაფრიდან მივდივართ ალგორითმის ფუნდამენტებთან (სვამთ ყავას) კოდის გამართულობის გარდა ის უნდა იყოს სწრაფი  დიდი ზომის ინფორმაციის დამუშავების დროს. პროგრმაირებაში დროის და ალგორითმების სირთულე (time and algorithm complexity) გამოიხატება სამი ნოტაციით  (პრინცპში უამრავი ალგორითმი და ნოტაცია არსებობს მაგრამ ჩვენ ყველას ვერ განვიხილავთ) და ესენია:

1.     Big O Notation O() ≤ (დიდი ო-ს ნოტაციები) ნაკლებია ან უდრის

2.     Big Theta Notation Ө () = (დიდი ტეტა-ს ნოტაციები) უდრის

3.     Big Omega Notation Ω()≥ (დიდი ომეგა-ს ნოტაციები) მეტია ან უდრის

სამივე ასახავს სიტუაციებს, რომელშიც კოდი შეიძლება მოხვდეს. Big Omega Notation-ში ინფორმაციის დამუშავების დრო ყოველთვის მეტია ან უდრის ინფორმაციას, ამიტომ ის არის Best case, პროგრამისტებს ყოველთვის აინტერესებთ ყველაზე ცუდი სიტუაცია სანამდეც კოდი შეიძლება მივიდეს, გამომდინარე აქედან ჩვენ ინტერეს და დროს Big Omega Notation-ზე არ დავხარჯავთ, შემდეგ მოდის Big O Notation სადაც ინფორმაცია შესაძლებლობების ფარგლებში სასურველია რო იყოს დროზე ნაკლები ან მას უდრიდეს მაინც, შესაბამისად Big O Notation არის Worst case, Big Theta Notation კი არის ნაზავი დიდი ო-ს და ომეგა ნოტაციების, ამიტომ მას average case  ეძახიან.

ალბათ გაუგებრად ჯღერს. წარმოიდგინეთ ყველა კომპიუტერს აქვს ინფორმაციის დამუშავების დრო და ინფორმაცია რომელიც უნდა დაამუშაოს. მასზე ბევრი ფაკტორი მოქმედებს, მაგალითად ინტერნეტის სისწრაფე, რამის სიდიდე, CPU-ს სიდიდე და ა.შ, მაგრამ ეს ჩვენ ვერ დაგვაინტერესებს იმიტომ რო ყოველთვის უნდა ვეძებოთ  ყველაზე ცუდი სიტუაცია სადაც ჩვენი კოდი აღმოჩდება, გამომდინარე აქედან ავიღოთ პირობითი დრო (5000 მილი სეკუნდი) რომელიც საჭიროა ინფორმაციის დასამუშავებლად. 5000 მილი სეკუნდი არის პირობითი სტანდარტული მონაცემი კომპიუტერის, ამ დროში ის ამუშავებს რაღაც ინფორმაციას.

 დაუშვათ თითო ელემენტის, ან ობიეკტი დავარქვათ თუ გინდათ, დამუშავებას უნდა 10 მილი სეკუნდი, მაშინ ჩვენი ფორულა იქნება 5000მლ + 10მლ(1), თუ გავზრდით ინფორმაციას, დამუშავების დროც გაიზრდება, 5000მლ + 20მლ(2) და ა.შ. ლოგიკა იმედია გასაგებია, დაუბრუნდეთ ყველაზე ცუდი ვარიანტის ძებნას, ჩვენ არასდროს არ ვიცით რა მოვა მომხმარებლისგან, სავარაუდოდ ვიცით, ან მიახლოებით ვიცით მაგრამ ზუსტი მონაცემი არ გვაქ, ამიტომაც ვანგარიშობთ ყველაზე ცუდ ვარიანტს, თუ ზუსტი ოდენობა არ ვიცით ინფორმაციის რომელიც უნდა დამუშავდეს მაშინ ლოგიკური იქნება ერთი ელემენტის დამუშავება ავღნიშნოთ N-ით და ჩვენი ფორმულა გახდება 5000 + 10(n), სადაც n უცნობი ოდენობაა. ახლა წარმოიდგინეთ პროგრამას წერთ საბანკო სექტორისთვის სადაც მილიონობით ტრანზაქცია ხდება დღეში, საქართველოში, ან საერთაშორისო კომპანიაზე მუშაობთ სადაც ტრანზაქციების ოდენობა მილიარდებს უდრის. მაშინ ჩვენი უცნობი ოდენობა მილიარდი ხდება, n – 1,000,000,000.  ფორმულა უფრო რომ დავხვეწოთ მოდით დრო ავღნიშნოთ T-თი (Time), ფორმულა კი იქნება შემდეგი სახის T(n) სადაც 5000 მილი სეკუნდს უკვე აღარ აქვს მნიშვნელობა იმიტომ რო მან ყველაზე ცუდი სიტუაციის სტატუსი მაშინ დაკარგა როცა ჩვენი პირობითი ოდენობა მილიარდი გახდა, გავიმეორებ ჩვენი ინტერესია მხოლოდ და მხოლოდ ყველაზე ცუდი ვარიანტები. 5000 მილი სეკუნდი არის კონსტანტური სიდიდე პრობლემის დროში, ის 5000 იქნება ყველგან, გამომდინარე აქედან კონსტანტური სიდიდე უინტერესოა, ჩვენი მთლიანი ინტერესი მივაპყროთ 10მლ(1)-ს,  T(n) სადაც დრო და ინფორმაცია პირდაპირ პროპორციულად იზრდება. 

კომპიუტერულ მეცნიერებაში Time Complexity- აფასებს დროს, რომელიც საჭირო იქნა განუსაზღვრელი ოპერაციების საწარმოებლად.

აქედან დაუბრუნდეთ Big Omega Notation-ს, სადაც დრო ყოველთვის მეტია ან უდრის დასამუშავებელ ინფორმაციას, ≥. დრო თუ ყოველტვის მეტია ან უდრის დასამუშავებელ ინფორმაციას მაშინ ის ინტერესის საგანი ვერ იქნება, იმიტომ რო კოდი ყოველთვის სწრაფად იმუშავებს თითქმის ყველა სიტუაციაში. დასკვნა Big Omega Notation არის Best Case Scenario, ჩვენი ინტერესი კი არის Worst Case Scenario.

                                                                     Big O Notation

დიდი ო-ს ნოტაციები კომპიუტერულ მეცნიერებაში გამოიყენება, რათა მოვახერხოთ დროზე დაყრდნობით ალგორითმების ეფეკტურობის დადგენა. რა დრო დაჭირდება ალგორითმს სხვა და სხვა სიდიდის ინფორმაციის მიღების დროს. როდესაც კოდური პრობლემის გადაჭრის დრო დგება, სავარაუდოდ გექნებათ არჩევანი რამოდენიმე ალგორითმს შორის, დიდი ო-ს ნოტაციების ცოდნა დაგეხმარებათ სწორი არჩევნის გაკეთებაში. თქვენი ამოცანა იქნება გააკეთოთ საუკეთესო არჩევანი სადაც დროის ფაკტორი ყოველთვის „ნაკლები ან უდრის - ≤“ იქნება შეყვანილ ინფორმაციაზე. შეყვანილი ინფორმაცია წარმოიდგინეთ როგორც მასივი, დაკავშრიებული სიები, სეტები ...

დიდი ო-ს ფორმულა არის O(n) სადაც O არის რაიმე სახის ფუნქცია, (მეთოდი) და n არის შეყვანილი ინფორმაცია მეთოდში. ის ეფეკტური რო იყოს აუცილებელია ყოველთვის ≤ იყოს დროზე. გამომდინარე აქედან, T(n) ≤ O(n) დრო ყოველთვის ნაკლები უნდა იყოს ინფორმაციაზე რათა კოდმა სწრაფად და ეფეკტურად იმუშაოს. ხშირად დამწყებ პროგრამისტებს უჩდებათ კითხვა, რა სიდიდის უნდა იქნეს O(n) რო კოდმა კარგად იმუშაოს? ამაზე დასაბუთებული პასუხი არ არსებობს, სიტუაციას გაჩნია, იმდენად დიდი, რომ კომფორტულად მოერგოს დროს, იმ სიდიდის რომ ჩაეტიოს T(n) ფორმულაში. თუ გაცდა მას მაშინ კოდი გახდება ნელი, არა ეფეკტური და გამოუსადეგარი. ნახეთ ფოტო:

ფოტოზე წიტელ ზოლად ნაჩვენებია ელემენტების ოდენობა მასივში, ან დაკავშრიებულ სიებში, არ აქვს მნიშვნელობა. O(n) = O(520), ჩვენი პირობითი დრო მაღლა იყო 5000 მილი სეკუნდი + 10მლ(520). ვინაიდან კონსტანტური დრო არ გვაინტერესებს, დრო იზრდება პირდაპირ პროპორციულად ელემენტების ზრდისა, T(n) = T(520) სადაც T არის 10 მილი სეკუნდი, თუ ერთი ელემენტის წაკითხვას დაჭირდება 10 მილი სეკუნდი 520 ელემენტის წაკითხვას დაჭირდება 5200 მილი სეკუნდი, მწვანე ზოლი ფოტოზე გვიჩვენებს თუ რა დრომდეა ოპტიმალური და ეფეკტური კოდის მუშაობა, როდესაც ის კვეთს ლურჯ ზოლს კოდი გახდება ნელი, ყოველ შემდეგ ჯერზე უფრო ნელი, სანამ არ მიაღწევს upper bound-ს. ჩვენი ამოცანა არის რო კოდის თავისუფალი ფრენა მოვაქციოთ დასახულ დროში, რათა დრო ყოველთვის ნაკლები იყოს შეყვანილი ინფორმაციის დამუშავების დროზე.   დიდი ო-ს ნოტაცია გვაძლევს რამოდენიმე არჩევანს, რათა მოვახდინოთ ოპტიმიზება კოდის და სწორი არჩევნის გაკეთება ვარიანტებს შორის. შევეცდები ყველა განვიხილო, რომელიმე თუ არ დამავიწყდა. განახებთ როგორ ხდება გარკვევა თუ რა ნოტაციით მუშაობას ალგორითმი, გასაუბრებებზე უყვართ ამ კითხვის დასმა, დაგიდებენ კოდს და მოგთხოვენ ნოტაციის დაწერას. ან ერთი და იგივე კოდს დაგაწერინებენ რამოდენიმე ალგორითმით და მერე მოგთხოვენ განიხილო რომელი რითი ჯობია ერთმანეთს ან რითი არ ჯობია. თუ კომპიუტერულ სამყაროში ცდილობთ შეაბიჯოთ ამის ცოდნა აუცილებელია.

მაშ ასე დიდი ო-ს ნოტაციები:

O(1) – Constant

O(n) – Linear

O(n^2) – Quadratic

O(n^3) – Cubic

O(log n) – Logarithmic

O(n*log(n)) – Linearithmic

O(2n), O(N!), O(nk) და ა.შ

1 - O(1) – Constant - კონსტანტური ნოტაცია, არის ყველაზე მარტივი ნოტაცია, მისი დამუშავების დრო არ ცდება კონსტანტურ დროს, მისთვის არ არის მნიშვნელოვანი რა სიდიდის ოპერაციასთან უწევს მუშაობა იმიტომ რომ,  რა სიდიდისაც არ უნდა იყოს ის ასრულებს მხოლოდ ერთ კონრეტულ ოპერაციას, მაგალითად. გამოაქვს მასივიდან ერთი ციფრი, ან გამოაქვს დაკავშირებული სიებიდან რომელიმე ციფრი რომელიმე კონკრეტული ინდექსიდან, გამოაქვს პირველი ან ბოლო ციფრი მასივიდან ან სიიდან. მისი ოპერაციის შესასრულებლად ყოველთვის ერთი და იგივე დროა საჭირო, ამიტომ ეძახიან კონსტანტურ ალგორითმს. ნახეთ მაგალითი:

ყველა ველის დამუშავებას ჭირდება გარკვეული დრო, დაუშვათ 5000 მილი სეკუნდი, როგორც დასაწყისში ავღნიშნეთ, ყველა ველზე ოპერაცია სრულდება ერთხელ. რამდენი ოპერაცია სრულდება საერთო ჯამში არსებითად მნიშვნელოვანი არ არის იმიტომ რო ინფორმაციის დამუშავება არ არის გარე ფაკტორებზე დამოკიდებული. 1 000 000 სიდიდის მასივიდან ციფრის გამოტანა ფოტოზე ნაჩვენებ მაგალითზე დაყრდნობით რომ გავაკეთოთ, შედეგი იგივე იქნება.

დიაგრამაში თუ წარმოვიდგენთ O(1) – Constant ის ასე გამოიყურება:

2 - O(n) – Linear -ნოტაცია მთლიანად დამოკიდებულია გარე ფაკტორზე, თუ მეთოდს ან რომელიმე ოპერაციას უწევს მთლიანი n-ის წაკითხვა, მაშინ ოპერაციას იმდენი ნაბიჯის გაკეთება უწევს რამდენი ელემენტიც შეყავს მომხმარებელს, მაგალითად 1000 ელემენტის წასაკითხად 1000 ოპერაციის წარმოება უწევს კომპიუტერს, რაც დროსთან პირდაპირ პროპორციულად იზრდება, ნახეთ მაგალითი.

Int I = 0; ამ ველზე ზუსტად ვიცი რო ოპერაცია ერთხელ სრულდება , ინტი არის 0. O(1) + num.length-ზე არ ვიცით ოპერაცია რამდენჯერ სრულდება, ანუ ის არის O(n), +  i++ არ ვიცით რამდენჯერ გაიზრდება, ისიც არის O(n), + ეკრანზე რამდენი ციფრი გამოვა ესეც არ ვიცით num[i] ასევე არის O(n). დავიანგარიშოთ: 1 + n + n + n კონსტანტური დრო არ გვჭირდება, 1 დაიაკრგება, გვაქ სამი n რომლებშიც უფრო ცუდი ვარიანტი ამ ეტაპზე არ გვაქ, გამომდინარე აქედან, ოპერაცია არის O(n) ნოტაციის მატარებელი. რაც ნიშნავს იმას რომ ინფორმაციის ზრდასთან ერთად მისი დამუშავების დროც პროპორციულად იზრდება, 1 ელემენტის დამუშავება 1 წამი, 2-ის 2 წამი, 1000 - ის 1000 წამი და ა.შ. ვნახოთ დიაგრამაზე როგორ გამოიყურება O(n)

3 - O(n^2) – Quadratic ნოტაციაც დამოკიდებულია გარე ფაკტორზე, განსხვავებით O(n)-ან მას გაორმაგებულად უწევს ყველაფრის კეთება, მაგალითად თუ მომხმარებლისგან ვიღებთ 1000 ელემენტს მაშინ მის წასაკითხად O(n^2)-ს დაჭირდება 1 000 000 ოპერაციის წარმოება, ნახეთ მაგალითი:

გამოიცნობთ ფოტოზე რომელი ნოტაცია გვაქ? პირველი ლუპი არის n, მეორე ლუპი არის აგრეთვე n და მესამე ლუპი გვაქ ისევ n. დავიანგარიშოთ, კონსტანტებს არ დავწერთ ამ ჯერზე, მხოლოდ n-ით ვიმუშავებთ. ჩაბუდებულ ლუპში გვაქ n * n, ჩვენი მასივი 5 ელემენტს შეიცავს ანუ 25 ოპერაცია შესრულდება, პირველი ლუპი ციფრს რო წაიკითხავს მეორე ლუპი მთლიან ეგზეკუციას მოახდენს, ანუ გვაქ (n^2) + n + 1; როგორც მაღლა ვახსენე ჩვენ ყოველთვის ყველაზე ცუდ ვარიანტს ვეძებთ, (n^2) დიაგრამაში ისეთი სისწრაფით გაიზრდება დროსთან მიმართებაში რო n-ს არანაირი მნიშვნელობა არ ექნება ნელი იქნება თუ არა. ამიტომ ალგორითმს ვაცილებთ ყველაფერს გარდა ყველაზე ცუდი სცენარისა და გვრჩება (n^2). მათემატიკაში ამას პოლინომიალი ქვია, თუ იცით რას ნიშნავს გაგება არ გაგიჭირდებათ. 

წარმოიდგინეთ მილიონობით ინფორმაცია რო შემოვა Quadratic რა ნელა იმუშავებს. Quadratic თავისუფლად შეიძლება linear ალგორითმად გადაკეთდეს, კოდურ დონეზე არ გაჩვენებთ მაგრამ ლოგიკურად თუ დაფიქრდებით მიხვდებიც რატო, ისევე როგორც cubic შეიძლება გახდეს  quadratic ან linear, თუმცა პირიქით არ არის სწორი,  linear-ის quadratic-ად გადაკეთება არ იქნება მართებული.

“linear is a subtype of quadratic.”

3- O(n^3) – Cubic მსგავსად linear და quadratic ნოტაციებისა ისიც გარე ფაკტორებზეა დამოკიდებული, მისი დრო მის წინამორბედებთან შედარებით ძალიან სწაფად იზრდება, რაც ამ ნოტაციას არ აყენებს საუკეთესო ნოტაციების სიაში, თუ დასამუშავებელი ელემენტების სიდიდე სულ უფრო და უფრო იზრდება. ნახეთ მაგალითი:

ფოტოზე გვაქ n*n*n = n^3; თუ დასამუშავებელი ელემენტების რაოდენობა 1000 უდრის, მაშინ ოპერაციების რაოდენობა იქნება 1 მილიარდი, რაც არც ისე სასურველია ხშირ შემთხვევაში. ვნახოთ დიაგრამაზე როგორ გაიზრდება დროსთან მიმართებაში.

4- O(log n) – Logarithmic ერთ-ერთი ყველაზე სწრაფი ნოტაცია პროგრამირებაში, როდესაც დიდი ზომის ინფორმაციასთან გვიწევს მუშაობა. წარმოიდგინეთ ლექსიკონში ვეძებთ სიტყვა „ჰიპერბოლას“ მნიშვნელობას, ყველამ ვიცით რო ძიებაში უნდა ჩავწეროთ ჰიპერბოლა და  ყველაფერი გვაქ ჰიპერბოლაზე და მასთან დაკავშრიებულ თემებზე. მაგრამ როგორ ხდება ეს. რამოდენიმე ვარიანტი განვიხილოთ. ადრე როცა კომპიუტერი არ არსებობდა ჩვენ წინაპრებს ყველა გვერდის სათითაოდ გადაშლა უწევდათ სასურველი ინფორმაციის მოსაძებნად, შეიძლება თვეებიც დაჭირვებოდათ ამისთვის. თუმცა ტექნიკის ხანაში, იგივე პრინციპით თუ მივყვებით ძიებას მაშინ გამოვა რო O(n) ალგორითმს ვიყენებთ. თუ ლექსიკონი 7000 გვერდიანია ყველა გვერდის წაკითხვა მოგვიხდება სათითაოდ რო სასურველ შედეგამდე მივიდეთ, კომპიუტერულ მეცნიერებაშიც კი მსგავსი ოპერაცია ნელია, ყველაზე კარგ ვარიანტში ჰიპერბოლა იქნება წიგნის დასაწყისში და მას ძალიან მალე ვიპოვით, დაგვჭირდება 0 წამი, მაგრამ ყველაზე ცუდ ვარიანტში ის იქნება წიგნის ბოლოში და მის საპოვნელად დაგვჭირდება 0.7 წამი. ჩვენი ამოცანაა ეს დრო შევამციროთ, პირველი აზრი რაც თავში გვიჩდება არის ის რომ ყოველი მეორე გვერდი წავიკითხოთ, ანუ დროს გავანახევრებთ, ფორმულა იქნება O(n/2) და დრო გახდება 0.3 წამი, მაგრამ ეს მიგვიყვანს შედეგამდე? შეიძლება იმ ნახევარში არ აღმოჩდეს ჰიპერბოლა რომელსაც წავიკითხავთ, მესამე ვარიანტია წიგნი გავყოთ შუაზე, ავირჩიოთ მხარე საითაც ჩვენი ვარაუდით იქნება ჰიპერბოლა და არჩეული მხარეც გავყოთ შუაზე, მერე გაყოფილი გავყოთ შუაზე და გავიმეორეთ ოპერაცია მანამ სანამ ხელში არ შეგვრჩება 1 გვერდი, რომელზეც ზუსტად ვიცით რომ ჰიპერბოლა არის, და ამ ნოტაციას ერქმევა O(log n). სამ ნოტაციაზე ვისაუბრეთ ლეკსიკონში სიტყვის საძიებლად, დროა გადავწყვიტოთ, რომელია მათ შორის უფრო ეფეკტური:

1-O(n) 7000 გვერდის წასაკითხად დაჭირდება 7000 ოპერაცია, თუ მეორე წიგნის წაკითხვაც მოგვიხდება იგივე გვერდების რაოდენობით, ოპერაციის ოდენობა 14 000 გახდება

2- O(n/2) 7000 გვერდის წასაკითხად ........

3- O(log n) 7000 გვერდის წასაკითხად დაჭირდება სავარაუდოდ 4-5 ნაბიჯის გაკეთება, ანუ მის მიერ ინფორმაციის დამუშავების დრო იქნება ისეთი სწრაფი რო გრაფაზეც ძლივს გამოჩდება.

ეს არის კლასიკური მაგალითი O(log n)-ის. BinarySearch. რომელიც ყოფს ინფორმაციას მანამ სანამ არ მივა სასურველ შედეგამდე. სამივე მაგალითზე დავამუშავეთ 10 000 000 რანდომ ნომერი, ნახეთ რამდენი საფეხუ დაჭირდათ ოპერაციის შესასრულებლად ალგორითმებს:

დააკვირდით რა დონემდე სწრაფია O(log n), სულ რაღაც 23 ნაბიჯში დაჭირდა 10 000 000 წასაკითხად. დიაგრამაში ის შემდეგნაირად გამოიყურება.

5-O(n*log(n)) – Linearithmic არის  ნაზავი O(n) და O(log n) -ის. ზედა მაგალითზე O(log n) ასრულებს ოპერაციას კონსტანტური სიდიდის ინფორმაციაში, თუმცა არის შემთხვევები როცა არ ვიცით რა სიდიდის ინფორმაციის დამუშავება გვიწევს, ამიტომ ვახდენთ ინფორმაციის დალაგებას და შემდეგ მის დამუშავებას რაც გვაძლევს, O(n log n)-ს, მისი მაგალითებია QuickSort და MergeSort. მათ მომავალში განვიხილავთ ახლა კი პრიმიტიული მაგალითი ვნახოთ Linearithmic ნოტაციის.

გარე ლუპში ნათელია, ნ-ჯერ ვკითხულობთ ინფორმაციას მაგრამ შიდა ლუპში ამ იმფორმაციას ვყოფთ შუაზე, დაუშვათ რანდომ ნომერი აღმოჩდა 15, მაშინ გარეთა ლუპმა 15ჯერ უნდა მოახდინოს ეგზეკუცია და ყველა ჯერზე შიდა ლუპმა 15 უნდა გაყოს 2=ზე, მაგალითად, 1 ეგზეკუცია გარეთა ლუპი - შიდა ლუპი 15/2 = 7: 7/2 = 3; 3/2 = 1; და ბრუნდება გარეთა ლუპში სადაც ი ხდება 2. რაც ნიშნავს იმას რომ პრინციპში ლუპის ეგზეკუცია ხდება განუსაზღვრელი ოდენობით, რომლის განუსაზღვრელი ოდენობა ახდენს განსაზღვრული ოდენობის O(log n) ეგზეკუციას. ალბათ ახლა გაუგებრად ჟღერს მაგრამ სტრუკტურულ მონაცემებზე საუბრის დროს მარტივად გაიგებთ ყველაფერს. ვნახოთ როგორ გამოიყურება ის გრაფაში:

კოდი თუ O(n*log(n)) ნოტაციით არის მაშინ შეგვიძლია ვთქვათ რომ კოდი არის საშუალო სიძლიერის.

ვნახეთ რამოდენიმე მაგალითი ნოტაციების, რომლებიც გამოიყენება კოდის ეფეკტურობის საზომად დროსთან მიმართებაში. ერთი შეგეხდვით ყველაფერი ნათელია. თუმცა ეს ასე არ არის, ხშირ შემთხვევაში O(n) , O(n^2) და გრაფაზე ნაჩვენები სხვა ნოტაციები პატარა ზომის ინფორმაციის დამუშავების დროს არიან გაცილებით სწრაფები ვიდრე O(log n) ან O(n log n) , როცა ნოტაციით შეეცდებით სისწრაფის გამოთვლას ყოველთვის დათვალეთ დეტალურად, მოძებნეტ ოპტიმალური ვარიანტი და მხოლოდ ამის შემდგომ გააკეთეთ არჩევანი.

სტანდარტული დიაგრამა.

დიაგრამა დიდი ზომის ინფორმაციასთან მუშაობის დროს.

დიაგრამა მცირე ზომის ინფორმაციასთან მუშაობის დროს. ხედავთ რო O(n) გარკვეულ პერიოდამდე გაცილებით სწრაფია log n-ზე.

                                   როგორ მოვახდინოთ ნოტაციის დადგენა?

მნიშვნელოვანია იცოდეთ თუ როგორ უნდა მოახდინოთ კოდის ნოტაციის დადგენა, ამისთვის საჭიროა:

1.     ალგორითმი O(1) ნოტაციით აწარმოებს ერთ ან რამოდენიმე კონსტანტურ ოპერაციას. მისი დადგენა ძალიან მარტივია, მაგალითად დავამატოთ n სიდიდის მასივს ელემენტი, ან მოვაკლოთ, ისევე როგორც ნებისმიერი ინდექსიდან ინფორმაცია გამოვიტანოთ ეკრანზე, აგრეთვე მთლიანი n-ის ერთი ოპერაციით ეკრანზე გამოტანა არის კონსტანტური ნოტაცია: public int printArray(int[]array) return array.length; და მაინც ერთი შეხედვით როგორ მივხდეთ რო ალგორითმი O(1)  ნოტაციის მატარებელია? თუ ოპერაცია ან ოპერაციების ერთობა გაქვთ ლუპების გარეშე მაშინ დიდი ვარაუდით ალგორითმი კონსტანტურია.  

2.     ალგორითმი O(n) ნოტაციით აწარმოებს n სიდიდის ოპერაციას, თუ წიგნს კითხულობთ თქვენ გიხდებათ მასში ყველა სიტყვის წაკითხვა, ანუ თქვენი მოქმედება დროის პირდაპირ პროპორციულია, მისი დადგენაც ნოტაციით მარტივია, ნებისმიერი რამ რაც თვლას ან წაკითხვას იწყებს პირველი ელემენტიდან და მიდის ბოლო ელემენტამდე არის O(n) ნოტაციის მატარებელი. For, while loops, იშვიათად if else statements.

3.     ალგორითმი O(n^2) ნოტაციით აწარმოებს ორჯერ n სიდიდის ოპერაციას. მაგალითად თუ სარგებლობთ ვაუჩერით, რომელსაც აქვს გარკვეული სიდიდის ჩამონათვალი საკვები პროდუკტების, რომლის შეძენაც შეგიძლიათ და მისი დახმარებით ცდილობთ სუპერმარკეტში საკვების შეძენას მაშინ თქვენ მოგიწევთ ყველა პროდუკტის ვაუჩერზე გადამოწმება და შემდგომ n სიდიდის დახლზე მისი მოძებნა და შეძენა, ანუ ყველა პროდუკტს ვაუჩერიდან ადარებთ პროდუკტს რომელიც დახლზე ალაგია. პროგრამულად რომ წარმოიდგინოთ ვაუჩერი არის გარე loop და დახლი არის შიდა loop. გამომდინარე აქედან n სიდიდის ლუპი სადაც ხდება n სიდიდის ლუპის ეგზეკუცია არის O(n^2) ნოტაციის მატარებელი. როგორც წესი ის ძალიან ნელია. იგივე პრინციპით ხდება O(n^3), 4, 5 და ა.შ დადგენა.

4.     ალგორითმი O(log n) ნოტაციით მუშაობს გასხვავებული პრინციპით, ყველა ეგზეკუციის შემდგომ ის ყოფს ელემენტების ოდენობას შუაზე, მაგალითად for loop რომლის ეგზეკუციაც ხდება n-ჯერ, მისი შემდგომი ეგზეკუცია მოხდება n/2, შემდგომი (n/2)/2 და ა.შ. ანუ თუ ხედავთ ოპერაციას რომელიც ყოველ ჯერზე ნახევრდება დიდი ვარაუდით ის O(log n) ნოტაციის მატარებელია.

5.     ალგორითმი O( n log n) ნოტაციით O(log n) ოპერაციას ასრულებს n-ჯერ. მსგავსად  O(n^2)-სა, ოღონდ გარეთა ლუპი n არის და შიდა ლუპი O(log n). წარმოიდგინეთ ეძებთ რაიმე ინფორმაციას დიდი ზომის დატაში, ყოფთ მას ყველა ჯერზე რათა ოპერაცია მალე შესრულდეს, ერთი განსხვავებით, თქვენ არ იცით რა სიდიდის არის დატა.

6.     ალგორითმი O(2^n), 3,4,5 ნოტაციით მაგალითებზე არ განგვიხილია, არ იყო ამის აუცილებლობა, მისი გამოყენება თითქმის არ ხდება, თუმცა როგორ უნდა დაადგინოთ სხვის კოდში მისი არსებობა აგიხსნით, წარმოიდგინეთ თქვენს საბანკო ბარათს აქვს პინ კოდი, პინ კოდი შედგება 4 ციფრისგან და ვიცით რო 4 ციფრი შეიძლება იყოს ნებისმიერი ციფრი 0-9-ე. როდესაც ბარათის გამოყენებას გადავწყვეტთ მისი ავთენტურობა რო დადგინდეს ვიწყებთ ყველა ციფრის პინის პირველ ციფრზე შედარებას, შემდგომ მეორე ციფრზე და ა.შ. ანუ პინი არის ჩვენთვის n სიდიდე და ციფრების რაოდენობა რომელზეც ხდება შედარება არის 10. გამომდინარე აქედან O(n^10). პინი რო ჩავსვათ n-ის ადგილას და ავიყვანოთ მეათე ხარისხში კოდს სავარაუდოდ მილიონი ოპერაციის წარმოება მოუწევს. კოდში მისი მოძებნაც მარტივად ხდება, ნებისმიერ სიდიდეს ნაბიჯ-ნაბიჯ თუ ვადარებთ n სიდიდეს მაშინ გვაქ ექსპონენციალური ნოტაცია.

7.     O(n!) არ გვისაუბრია , არც ამის აუცილებლობა არსებობდა იმიტომ რო მისი მაგალითები სხვა ბლოგებში ბლომად გაქვთ ნანახი, გადახედეთ ბლოგს რეკურსიაზე, ალგორითმი ხშირ შემთხვევაში  O(n!)-ის ნოტაციის მატარებელია თუ ის n სიდიდის ფაკტორიალს თვლის.  

თქვენ ჩვევად უნდა იქციოთ (time and space complexity) - ით ხელმძღვანელობა  კოდის წერის დროს, ის ყოველთვის დაგეხმარებათ კოდის ოპტიმიზირებაში, ასიმპტოტიკური  ანალიზი ძლიერი ხელსაწყოა თქვენ პროგრამულ გარდერობში, პოლინომიალი ვახსენე მაღლა სადაც კონსტანტურ ღირებულებებს აზრი ეკარგება ნოტაციების დროს, თუმცა ზოგჯერ ესეც მცდარია, სიტუაციას გააჩნია. კარგი ინჟინერი პოულობს ბალანს  - ინფორმაციას, დროსა და მეხსიერებას შორის, თან ამავდროულად არ ივიწყებს რომ კოდი მარტივად განახლებადი და წაკითხვადი რომ უნდა იყოს.  ბლოგი მაქსიმალურად მარტივ ენაზე არის დაწერილი რაც ფიქრისკენ გიბიძგებთ, შედეგად კი იმედია უფრო ღრმად „ჩაუჯდებით“ ნოტაციებს, ალგორითებს და სირთულეებს. წარმატებებს გისურვებთ. 

სასარგებლო ინფორმაცია: გადაავლეთ თვალი - asymptotic notation, time complexity, space  complexity, polynomial time, exponential time, algorithms analysis.