დაულაგებელ სიმრავლეში c-ს ტოლი ელემენტის წაშლის რეკურსიული ალგორითმი

Erase (A,c)

{

if (n=0 ) return A;

if (an = c ) { ამოშალე ეს ელემენტი A მიმდევრობიდან ; return A; }

n–;

return Erase(A,c);

}

 

სისწორის დამტკიცება :

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

 

ბიჯების რაოდენობა :

როცა n=0 , T(0) = 2 // შედარება და დაბრუნება იგივე ცარიელი სიმრავლისა .

T(Erase(A(n),c)) = 3 + T(Erase(A(n-1),c)) = . . . = T(0) + 3n = 3n+2 = O(n)

5 thoughts on “დაულაგებელ სიმრავლეში c-ს ტოლი ელემენტის წაშლის რეკურსიული ალგორითმი

    • საკმაოდ ბევრს აინტერესებს და არის ადამიანები ვისაც ეს გამოცდისთვის ეხმარება🙂🙂🙂

      თან პირველ რიგში ეს თემა მე მაინტერესებს და ვდებ ხოლმე ამაზე პოსტებს🙂

      • არაფერს Dixtos ,
        ვიცი რომ ცოტაა ვისაც აინტერესებს მაგრამ მაინც ვწერ რადგან თავადაც მაინტერესებს ეს სფერო🙂

Leave a Reply / უპასუხე

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / შეცვლა )

Twitter picture

You are commenting using your Twitter account. Log Out / შეცვლა )

Facebook photo

You are commenting using your Facebook account. Log Out / შეცვლა )

Google+ photo

You are commenting using your Google+ account. Log Out / შეცვლა )

Connecting to %s