כמה שאלות במבוא למדמ"ח

[Fluff]

היי, אני אשמח לעזרה בשאלות הבאות:

1. http://i.imgur.com/U5IF5NJ.png?1

התשובות הן http://www.codecogs.com/gif.latex?%5Csqrt%7Bn%7D לזמן ו-http://www.codecogs.com/gif.latex?logn למקום, איך אפשר להגיע לזה?

 

 

2. http://i.imgur.com/1gVJ5Al.png?1

סליחה התמונה יצאה קצת מוזרה... בכל מקרה הקוד הזה מחליף בין מיקום של מחרוזות בתוך מערך של מחרוזות.

מישהו במקרה זוכר/יודע מה char** אומר כשהוא בחתימה של הפונקציה ו-char* אומר כשהוא בקוד עצמו? (הכוכביות אמורות להיות מימין.)

בכללי, אם אני לא טועה, חשבתי ש-char* גם בחתימה וגם בקוד עצמו אומר שזה מצביע לתו הראשון במחרוזת, אבל הקוד הנ"ל בילבל אותי.

 

תודה רבה מראש :-)

[Paranoid]

שאלה 1 בנפנוף ידיים:

כל פעם n מתחלק ב2 אז יהיו סה"כ logn קריאות לפונקציה ובכל קריאה סיבוכיות המקום היא O(1) לכן בסך הכל סיבוכיות המקום תהיה logn.

לגבי הזמן- הלולאה בעצם מוסיפה 2n/3 לm כלומר סדר גודל של n. אבל היא מוסיפה את זה בצורה של 1+2+3+4... אם נניח שהיא עושה k איטרציות אז כמה שהיא הוסיפה זה סדר גודל של k^2 (סכום סדרה חשבונית). כלומר בשביל להוסיף סדר גודל של n היא צריכה לעשות סדר גודל של (שורש n) איטרציות.

אז בעצם יש פה סיבוכיות זמן של (שורש n) + (שורש n/2) + (שורש n/4) +... (סך הכל חיבור של logn איברים).

אפשר לראות שזה סדר גודל של שורש n.