ძირითადი მასალა

კომპიუტერული მეცნიერება

კურსი: კომპიუტერული მეცნიერება > თემა 1

გაკვეთილი 6: რეკურსიული ალგორითმები

რეკურსიული ფუნქციების ეფექტურობის გაუმჯობესება

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

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

მაგალითად, JavaScript-ის ეს კოდი იძახებს factorial()-ს 4-ჯერ:

factorial(0);
factorial(2);
factorial(5);
factorial(10);

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

კოდის ხაზი	რეკურსიული გამოძახებები	ჯამური გამოძახებები
`factorial(0)`		1 გამოძახება
`factorial(2)`	`factorial(1)` → `factorial(0)`	3 გამოძახება
`factorial(5)`	`factorial(4)` → `factorial(3)` → `factorial(2)` → `factorial(1)` → `factorial(0)`	6 გამოძახება
`factorial(10)`	`factorial(9)` → `factorial(8)` → `factorial(7)` → `factorial(6)` → `factorial(5)` → `factorial(4)` → `factorial(3)` → `factorial(2)` → `factorial(1)` → `factorial(0)`	11 გამოძახება

აღვნიშნოთ, რომ factorial(10) აკეთებს ფუნქციის 11 გამოძახებას და მათგან 6-ს აქვს ზუსტად ერთი და იგივე არგუმენტები და დასაბრუნებელი მნიშვნელობები, რაც ფუნქციის წინა გამოძახებებს, რომლებიც გაკეთდა factorial(5)-ის დროს.

ფაქტორიალის მემოიზაცია

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

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

თუ n = 0, დააბრუნე 1
წინააღმდეგ შემთხვევაში, თუ n არის მემოში, დააბრუნე მემოს მნიშვნელობა n-ისთვის
წინააღმდეგ შემთხვევაში,
- გამოთვალე left parenthesis, n, minus, 1, right parenthesis, !, times, n
- დაიმახსოვრე შედეგი მემოში
- დააბრუნე შედეგი

ეს ალგორითმი ამოწმებს შემომავალ მონაცემებს მემოში სანამ სანამ პოტენციურად „ძვირ“ რეკურსიულ გამოძახებას გააკეთებს. მემო უნდა იყოს ეფექტური საძიებო დროის მქონე მონაცემთა სტრუქტურა, როგორიცაა ჰეშ ცხრილი O, left parenthesis, 1, right parenthesis საძიებო დროით.

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

როდესაც მემოიზაცია არის იმპლემენტირებული, კომპიუტერს შეუძლია, ნაკლები ჯამური გამოძახება გააკეთოს factorial()-ის გამეორებული გამოძახებების დროს():

კოდის ხაზი	რეკურსიული გამოძახებები	ჯამური გამოძახებები
`factorial(0)`		1 გამოძახება
`factorial(2)`	`factorial(1)` → `factorial(0)`	3 გამოძახება
`factorial(5)`	`factorial(4)` → `factorial(3)` → `factorial(2)`	3 გამოძახება
`factorial(10)`	`factorial(9)` → `factorial(8)` → `factorial(7)` → `factorial(6)` → `factorial(5)`	6 გამოძახება

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

ფიბონაჩის მემოიზაცია

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

შევხედოთ მარტივ მაგალითს, ფიბონაჩის რიცხვების დამგენერირებელი ალგორითმი.

ფიბონაჩის მიმდევრობა არის რიცხვების ცნობილი მიმდევრობა, რომელშიც ყოველი მომდევნო რიცხვი არის მის წინა ორი რიცხვის ჯამის ტოლი. მიმდევრობის პირველი ორი წევრი განსაზღვრულია 0-ად და 1-ად. ამის შემდეგ, შემდეგი რიცხვი არის 1 (მიიღება 0, plus, 1-ით) და რიცხვი მის შემდეგ არის 2 (მიიღება 1, plus, 1-ით) და ა.შ.

ფიბონაჩის პირველი 10 რიცხვი:

0, comma, 1, comma, 1, comma, 2, comma, 3, comma, 5, comma, 8, comma, 13, comma, 21, comma, 34

ფიბონაჩის მე-n რიცხვის დამგენერირებელი მარტივი რეკურსიული ფუნქცია შემდეგნაირად გამოიყურება:

თუ n არის 0 ან 1, დააბრუნე n
წინააღმდეგ შემთხვევაში, დააბრუნე start text, f, i, b, o, n, a, c, c, i, end text, left parenthesis, n, minus, 1, right parenthesis, plus, start text, f, i, b, o, n, a, c, c, i, end text, left parenthesis, n, minus, 2, right parenthesis

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

როცა n, equals, 5, კომპიუტერი აკეთებს 15 გამოძახებას:

ხანის აკადემიის ვიდეოების მომთავსებელი

Recursive Fibonacci Calls (Diagrammed)ვიდეოს ტრანსკრიპტის ნახვა

შევნიშნოთ ფიბონაჩის ფუნქციის მრავალჯერადი გამოძახება შემომავალ მონაცემებზე 3, 2, 1 და 0. როცა შემომავალი მონაცემები იზრდება, ეს უფრო და უფრო არაეფექტური ხდება. fibonacci(30)-ის გამოძახება შედეგად გვაძლევს კომპიუტერის მიერ fibonacci(2)-ის ნახევარ მილიონჯერ გამოძახებას.

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

ფიბონაჩის რეკურსიული ალგორითმის მემოიზაციური ვერსია შემდეგნაირად გამოიყურება:

თუ n არის 0 ან 1, დააბრუნე n
წინააღმდეგ შემთხვევაში, თუ n არის მემოში, დააბრუნე მემოს მნიშვნელობა n-ისთვის
წინააღმდეგ შემთხვევაში,
- გამოთვალე start text, f, i, b, o, n, a, c, c, i, end text, left parenthesis, n, minus, 1, right parenthesis, plus, start text, f, i, b, o, n, a, c, c, i, end text, left parenthesis, n, minus, 2, right parenthesis
- შეინახე შედეგი მემოში
- დააბრუნე შედეგი

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

n, equals, 5-ისთვის კომპიუტერი აკეთებს 9 გამოძახებას:

ხანის აკადემიის ვიდეოების მომთავსებელი

Memoized Recursive Fibonacci Calls (Diagrammed)ვიდეოს ტრანსკრიპტის ნახვა

ალგორითმის თავდაპირველი ვერსია საჭიროებდა ფუნქციის 15 გამოძახებას, ასე რომ, მემოიზაციამ ამოაგდო ფუნქციის 6 გამოძახება.

ცხრილზე ნაჩვენებია n, equals, 5-იდან n, equals, 10-მდე გამოძახებების რაოდენობები:

n	თავდაპირველი	მემოიზაციით
5	15	9
6	25	11
7	41	13
8	67	15
9	109	17
10	177	19

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

მემოიზებული ალგორითმი საჭიროებს მეტ ადგილს; ის საკმარისი უნდა იყოს მემოსთვის n-ის ყოველი დაბრუნებული მნიშვნელობის შესანახად.

ქვემოდან ზემოთ

ზოგჯერ, რეკურსიული ალგორითმის ეფექტურობის გაუმჯობესების საუკეთესო გზა არის რეკურსიის საერთოდ არგამოყენება.

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

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

თუ n არის 0 ან 1, დააბრუნეთ n
წინააღმდეგ შემთხვევაში,
- შექმენით ცვლადი start text, t, w, o, B, e, h, i, n, d, end text, რათა დავიმახსოვროთ left parenthesis, n, minus, 2, right parenthesis-ის შედეგი და ინიციალიზაციისას მივანიჭოთ მნიშვნელობა 0
- შექმენით ცვლადი start text, o, n, e, B, e, h, i, n, d, end text, რათა დავიმახსოვროთ left parenthesis, n, minus, 1, right parenthesis-ის მნიშვნელობა და ინიციალიზაციისას მივანიჭოთ მას მნიშვნელობა 1
- შექმენით ცვლადი start text, r, e, s, u, l, t, end text, რათა შევინახოთ საბოლოო შედეგი და ინიციალიზაციისას მივანიჭოთ მას მნიშვნელობა 0
- გავიმეოროთ ეს left parenthesis, n, minus, 1, right parenthesis-ჯერ:
  - განვაახლოთ start text, r, e, s, u, l, t, end text როგორც start text, t, w, o, B, e, h, i, n, d, end text-ს პლუს start text, o, n, e, B, e, h, i, n, d, end text
  - განვაახლოთ start text, t, w, o, B, e, h, i, n, d, end text
    - შევინახოთ მასში start text, o, n, e, B, e, h, i, n, d, end text-ის მიმდინარე მნიშვნელობა
  - განვაახლოთ start text, o, n, e, B, e, h, i, n, d, end text
    - მასში შევინახოთ start text, r, e, s, u, l, t, end text-ის მიმდინარე მნიშვნელობა
  - დავაბრუნოთ start text, r, e, s, u, l, t, end text

ეს მიდგომა არასდროს აკეთებს რეკურსიულ გამოძახებას; სანაცვლოდ ის იყენებს იტერაციას ნაწილობრივი შედეგების დასაჯამებლად და რიცხვის გამოსათვლელად.

თუ გსურთ JavaScript-ში იმპლემენტირებული ქვემოდან ზემოთ მიდგომის გაშვების ვიზუალიზაცია, უყურეთ ამ ვიდეოს ან გაუშვით ვიზუალიზაცია თქვენით.

ქვემოდან ზემოთ ალგორითმს აქვს იგივე O, left parenthesis, n, right parenthesis დროის კომპლექსურობა, რაც მემოიზებულ ალგორითმს, მაგრამ მას სჭირდება მხოლოდ O, left parenthesis, 1, right parenthesis ადგილი, ვინაიდან ის მხოლოდ სამ ცვლადს ინახავს ერთდროულად.

დინამიკური პროგრამირება

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

დინამიკური პროგრამირების გამოყენება შეიძლება მაშინ, როცა პროგრამას აქვს ოპტიმალური ქვესტრუქტურა და თანამკვეთი ქვეამოცანები. ოპტიმალური ქვესტრუქტურა ნიშნავს, რომ ამოცანის ოპტიმალური ამოხსნა შესაძლებელია, შეიქმნას მისი ქვეამოცანების ოპტიმალური ამოხსნებისგან. სხვა სიტყვებით, fib(5)-ის ამოხსნა შესაძლებელია fib(4)-ითა და fib(3)-ით. თანამკვეთი ქვეამოცანები გვხვდება მაშინ, როცა ქვეამოცანა იხსნება მრავალჯერ, რაც ვნახეთ მაშინ, როცა fib(5)-მა გააკეთა ტიპურად რეკურსიული fib(3)-ისა და fib(2)-ის მრავალჯერადი გამოძახება.

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

[ატრიბუცია]

გსურთ, შეუერთდეთ დისკუსიას?

შესვლა

დავალაგოთ:

პოსტები ჯერ არ არის.

გესმით ინგლისური? დააწკაპუნეთ აქ და გაეცანით განხილვას ხანის აკადემიის ინგლისურენოვან გვერდზე.