שתי שאלות בניתוח סיבוכיות.

[gil levi]

שתי שאלות בניתוח סיבוכיות.

1. מה סיבוכיות זמן הריצה של הפונ' הבאה כאשר קוראים לה עם איבר ממויין בסדר יורד ועם k=0:

Rec_Build_Strong_Heap(A,k) if (2*k+1<=n-1) l=Rec_Build_Strong_Heap(A,2*k+1) if (2*k+2<=n-1) r=Rec_Build_Strong_Heap(A,2*k+2) root=AllocateMemory key[root]=A[k] if (2*k+1<=n-1) left[root]=l parent[l]=root else left[root]=NIL if (2*k+2<=n-1) right[root]=r parent[r]=root else right[root]=NIL return root​

הפונ' מקבלת מערך ממוין (בסדר יורד) A ואינדקס k ובונה ערימת מקסימום חזקה שהשורש שלה הוא האיבר A[k] zzz. ערימת מקסימום חזקה היא ערימת מקסימום שבה כל האיברים בשכבה מסוימת קטנים מכל האיברים בשכבה שמעליה. ברור לי שהסיבוכיות היא Θ zzz אבל הסתבכתי בנסיון להוכיח את זה. ניסיתי להראות שכאשר קוראים לפונ' עם k=0 אז היא מבצעת מספר קבוע של פעולות לכל אחד מn האיברים אבל הסתבכתי בנסיון להראות שהיא אכן "עוברת" על כל איבר רק פעם אחת בלבד ועוברת על כל האיברים. מה שעשיתי זה להגדיר את הפונ':

l(k)=2*k+1 r(k)=2*k+2​

ואז ניסיתי להראות שכל שני ביטויים של הרכבות של l ו k (למשל l∘k∘k∘k∘l∘l∘l∘k∘l∘k) תמיד יתנו פונ' שונות ושעל ידי ההרכבות שהפונ' Rec_Build_Strong_Heap אפשר להגיע לכל j כך ש j בין 1 לn. כמו שאמרתי, הסתבכתי ונדמה לי שקצת נסחפתי... למישהו יש רעיון פשוט יותר? 2. אני צריך לפשט את הביטוי:

lg( 2!*4!*8!*...*((n+1)/4)! )​

ולהציג אותו במונחי Ω. הצלחתי להגיע ל Ωzzz אבל קשה לי להאמין שזה הדוק. הנה מה שעשיתי:

lg( 2!*4!*8!*...*((n+1)/4)! ) = lg(2!) + lg(4!) + lg(8!) + ...+ lg((n+1)/4)! = 2*lg(2) + 4*lg(4) 8*lg(8) + ... + ((n+1)/4)*lg((n+1)/4) >= 2*lg(2) + 4*lg(2) + 8*lg(2) + ....((n+1)/4)*lg(2) = Ω​

המעבר השני נובע מהזהות ׂlg(t!) = Θ(t*lg(t)) zzz, את המעבר האחרון עשיתי באמצעות סכום סידרה הנדסית. האם החסם הדוק או שאפשר לשפר אותו? תודה מראש.

 

[vinney]

המם...

לגבי 1 - זה פונקציה רקורסיבית, תבדוק אם אתה יכול להשתמש במשפט האב להוכחת הסיבוכיות. לגבי 2 - המעבר האחרון שלך לא ברור לי... יש לך

2*lg(2) + 4*lg(4)+ 8*lg(8) + ... + ((n+1)/4)*lg((n+1)/4) שזה 2*lg(2) + 4*lg(4)+ 8*lg(8) + ... + ((n+1)/4)*(lg((n+1))- log(4)) שזה 2*lg(2) + (4-(n+1)/4)*lg(4) 8*lg(8) + ... + ((n+1)/4)*lg((n+1) שזה גדול מ (4-(n+1)/4)*lg(4) + ((n+1)/4)*lg(n+1)) שזה בתורו גדול מ (N+1)log(N+1)​

כך שבאומגה הייתי שםNLOGN... אני מתלבלב לגמרי? כי יכול להיות

 

[gil levi]

תודה רבה.

 

[אולף]

לגבי השאלה השנייה

הביטוי שלך שווה ל

sigma(i=1 to n/8)log(2i!) >= sigma(i=n/16 to n/8)log(2i!) >= >= sigma(i=n/16 to n/8)log((2*n/16)!) = n/16*log((2*n/16)!) = n/16*log((n/8)!) same trick with halving the sigma log((n/8)!) = sigma(1 to n/8)log(i!) >= sigma(n/16 to n/8)log(i!) >= sigma(n/16 to n/8)log((n/16)!) = n/16*log(n/16) = OMEGA(nlogn) n/16*OMEGA(nlogn) = OMEGA(n^2 * logn)​

 

[אולף]

אגב

לגבי מה שכתבת בתשובה שלך לשאלה השנייה:

lg( 2!*4!*8!*...*((n 1)/4)! ) = lg(2!) lg(4!) lg(8!) ... lg((n 1)/4)! = 2*lg(2) 4*lg(4) 8*lg(8) ... ((n 1)/4)*lg((n 1)/4) >= 2*lg(2) 4*lg(2) 8*lg(2) ....((n 1)/4)*lg(2) = ? הזהות

log2! = 2log2​

אינה נכונה. הזהות שנכונה היא הזהות שציינת בסוף כאילו בה השתמשת, אבל אי אפשר להשתמש בה למספרים קבועים, אלא רק כחסם אסימפטוטי. בתשובה שלי הקודמת הראיתי לך דרך פשוטה איך להוכיח את אותה הזהות (כיוון אחד למעשה, של אומגה).​