დალაგებულ A სიმრავლეში, с-ს ტოლი ელემენტის ჩასმის რეკურსიული ალგორითმი

 

InsertFast_Recursion (a1,a2, . . . , an , c )

{

if ( c <= a1 ) A = (c , a1,a2, . . . , an ) ; return (A) ;

if ( c >= an ) A = (a1,a2, . . . , an , c ) ; return (A) ;

static min = 1 ;

static max = n;

i = (min+max) / 2;

if ( ai-1 <= c <= ai )

{

A = (a1, a2 , . . . , ai-1 , c , ai, . . . , an ) ;

return (A) ;

}

if ( ai <= c <= ai+1 )

{   A = (a1, a2 , . . . , ai , c , ai+1, . . . , an ) ;       return (A) ;    }

if ( c > ai  ) min = i ;

else max = i;

}

return  InsertFast_Recursion (a1,a2, . . . , an , c );

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

T(InsertFast(A(n),c)) =9 + T(InsertFast(A(n/2),c) = . . . = 9*logn + T(0) + 8 (while-მდე 8 ბიჯი სრულდება) = O(logn)

 

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

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

3 thoughts on “დალაგებულ A სიმრავლეში, с-ს ტოლი ელემენტის ჩასმის რეკურსიული ალგორითმი

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

    • მე მინდა , მსიამოვნებს და ვწერ და საკმაოდ ბევრსაც ადგება . შენ ნუ იღელვებ :)) :დ

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