מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/תת-סידרה עולה ארוכה ביותר ביעילות/תשובה

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

נגדיר את אורך כ.

  1. בפסוודו-קוד הבא, קריאה לLIS-Length(i) תחזיר את אורך הLIS שאיברו האחרון הוא
   האיבר ה בסדרה. (כדי למצוא את אורך הLIS הכללי, יש לבדוק את המקסימום
   בלולאה).
 
1		L = Make-Array(n)

2		for i in [1, ..., n]
3			L[i] = Nil


LIS-Length(i)
1		'''if L[i] == Nil'''
2			if i == 1
3				'''L[i] = 1'''
4				return 1
	
5			'''L[i] =''' max = 1
	
6			for j in [1, ..., i - 1]
7				if X[j]  X[i]
8					guess = 1 + LIS-Length(j)
9					if guess > max
10						'''L[i] =''' max = guess

11		'''return L[i]'''
 1-3 מייצרות מערך (גלובלי) שכל אחד מאיבריו מאותחל לNil.‏ 6-10 של LIS-Length, פועלות בדיוק לפי נוסחת הנסיגה לאורך הLIS שכבר ראינו (ושאת נכונותה כבר
   הראינו). המערך L, בפרט ב1 של
   LIS-Length, מטפלות במצב בו הפונקציה נקראת עם פרמטרים שאתם היא כבר נקראה
   בעבר.
 נעבור בלולאה, ונקרא לLIS-Length(1),‏‏‏ LIS-Length(2),‏ ..., LIS-Length(n) (לפי סדר זה).
   נשמור את המקסימום המתקבל מהקריאות, ואת האינדקס בו התקבל מקסימום זה. בגלל הmemoization, ברור שLIS-Length(i) היא  (כי  היא ). לכן זמן הריצה הוא .‏ ‏ חוץ מכך ישנו האתחול 1-3 שאורך . הזמן הכולל, לכן, הוא .
  1. ראשית נשנה מעט את הפסוודו-קוד הקודם. השינויים מסומנים כך.
1		L = Make-Array(n)
2		'''P = Make-Array(n)'''

3		for i in [1, ..., n]
4			L[i] = Nil


LIS-Length(i)
1		if L[i] == Nil
2			if i == 1
3				return 1

4			L[i] = 1
5			'''P[i] = 0'''

6			for j in [1, ..., i - 1]			
7				if X[j]  X[i]
8					if 1 + LIS-Length(j) > L[i]
9						L[i] = 1 + LIS-Length(j)
10						'''P[i] = j'''

11		return L[i]
 המערך הגלובלי P מתאר בכניסה ה את אינדקס האיבר
   הקודם בסדרה.
 בפסוודו-קוד הבא, קריאה לPrint-LIS(i) תדפיס את הLIS שאיברו האחרון הוא האיבר
   ה בסדרה. כדי להדפיס את הLIS הכללי, יש לקרוא לו עם האינדקס שמצאנו
   בסעיף הקודם.
 
Print-LIS(i)
1		if i > 0
2			Print-LIS(P[i])

3		Print(i)
 קל לראות שהסיבוכיות עדיין : השינויים בLIS-Length אינם משנים את סיבוכיותה; כל קריאה לPrint-LIS(i) מורידה הארגומנט שלה ב1, ולכן היא יכולה להיקרא לכל היותר  פעמים. הסיבוכיות, לכן, היא  +  = .