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