מבני נתונים חסם סיבוכיות על פונקציה

[ohad]

טוב זו הפונקציה הלא מסובכת:

http://i.imm.io/LApE.png

וזה הניתוח שלי:

 

לולאת ה for  הפנימית מתבצעת

[jstex]\frac{n}{\sqrt{i}}[/jstex]

פעמים (שניהם לא משתנים במהלך הלולאה),

הלולאה החיצונית רצה מ i=1 עד i=n

לכן סה"כ יש: [jstex]T(n)=\sum_{i=1}^{n}\cdot O\left(\frac{n}{\sqrt{i}}\right)=O\left(n\cdot\sum_{i=1}^{n}\frac{1}{\sqrt{i}}\right)=

[/jstex]

איך אני נפטר מהסכום הזה? אפשר לחסום אותו ע"י n אבל זה נראה לי גדול מידי.

[incog]

זו שאלה טובה, רעיון שעלה לי (יתכן שתוכל למצוא חסמים יותר טובים)

זה לחסום את הסכום על ידי:

 

 

 

אינטגרל על הפונקציה אחד חלקי שורש x כשהאינטגרל הולך מ-1 עד n.

[ohad]

תודה, מוזר שאין משהו יותר טוב.

נקווה שזה יצא משהו נורמלי...

אני לא אוהב אינטגרלים  :cry:

 

(השורות הריקות אצלך באמצע בכוונה או שהיה אמור להיות שם משהו?)

[incog]

תודה, מוזר שאין משהו יותר טוב.

נקווה שזה יצא משהו נורמלי...

אני לא אוהב אינטגרלים  :cry:

 

(השורות הריקות אצלך באמצע בכוונה או שהיה אמור להיות שם משהו?)

 

בהחלט יתכן שיש קירוב יותר טוב (אני אבל לא מכיר נוסחא כמו שיש לסכום של אחד חלקי n, ונדמה לי שזה הקירוב האסימפטוטי הטוב ביותר).

לגבי האינטגרל זה אינטגרל פשוט של x^-1/2 .

 

הרווח שיצא הוא במקרה, אני לא יודע למה אבל משום מה בפורום החדש לפעמים כשאני כותב רווח של שורה זה אחרי זה מופיע כרווח של יותר שורות.

[ohad]

נקווה שזה יספק את המתרגל העייף שיבדוק את התרגיל...

 

אכן באג מוזר, חשבתי כבר ששמת איזה תמונה/נוסחה להמחשה והאינטרנט במעונות החליט שהיא לא חשובה