שאלה בסיבוכיות

[גודבאר]

שאלה בסיבוכיות

מה זמן ריצה של קטע הקוד הבא? k = n w while k > 2 w k = k^(1/3) w תודה

 

[freak2100]

התחלה...

מה שקורה זה אתה עושה כל פעם שורש שלוש, ז"א:

(((k^(1/3))^(1/3))^......)^(1/3)))...) <= 2​

אתה מוציא בעצם n פעמים שורש שלישי עכשיו, לפי חוקי המתמטיקה, זה שווה ל:

k^((1/3)^n) <= 2​

ולכן:

log(k^((1/3)^n)) <= log(2) (1/3)^n*log(k) <= log(2) (1/3)^n <= log(2)/log(k) 3^n >= log(k)/log(2) n*log(3) >= log(log(k)/log(2)) n >= log(log(k)/log(2))/log(3)​

עכשיו, או שעשיתי טעות איפשהו בדרך, או שצריך איכשהו להמשיך לפשט את זה...

 

[vinney]

עשית טעות

זה: " אתה מוציא בעצם n פעמים שורש שלישי" לא נכון.

 

[freak2100]

התכוונתי n מבצינת מספר האיטרציות...

לא שמתי לב שn מופיע גם בקוד שלו, הכוונה הייתה שn בסופו של דבר יבטא את הסיבוכיות בעזרת k... הייתי צריך לכתוב את זה

לא שזה אומר שלא טעיתי בכל זאת, פשוט נראה לי שזה רק עניין של הגדרות לא מובנות

 

[vinney]

n לא צריך לבטא סיבוכיות בעזרת K

אלא אתה צריך לבטא את הסיבוכיות בעזרת K. לא מבין על איזה n אתה מדבר ומאיפה המצאת אותו.

 

[freak2100]

נכון, שכח מn, מה שהתכוונתי

זה לעשות דבר כזה נגדיר נניח פונקציה

f(k)​

שתבטא את מספר האיטרציות של התוכנית (בשביל למצוא את הסיבוכיות נצטרך למצוא חסם לf) עכשיו, אם יש f(k) איטרציות, יש לנו בעצם משהו כזה:

k^((1/3)^f(k)) <= 2​

כי אנחנו כן מוציאים f(k פעמים שורש שלישי של k... עכשיו על אותו עקרון בסוף מגיעים ל:

f(k) >= log(log(k)/log(2))/log(3)​

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

עכשיו זה בסדר?

 

[vinney]

קל לבלבל אותך אני רואה../images/Emo13.gif

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

 

[freak2100]

אה, נכון ../images/Emo3.gif

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

log(log)​

זה נכון?

 

[johnny d]

בערך, אבל למה את מסתבך

סיבוכיות הזמן היא לוגריתמית בלבד. הקלט הוא מספר בעל m ביטים, כלומר m = log n בכל איטרציה מקצצים את המספר לכ-שליש מספרותיו עד לתנאי סיום כלשהו, ולכן מדובר ב- log m

 

[johnny d]

(גודל הקלט חייב להיות בביטים)

 

[freak2100]

תראה, לא למדתי אף פעם את הנושא

לעומק (עדיין לא היה לי קורס מתקדם בנושא), אבל - למה? הרי אם במקום לעשות שורש היית מחלק - אז זאת הייתה סיבוכיות אלגוריתמית אז אתה רוצה להגיד לי שזה אותו דבר?

 

[vinney]

תלוי איך אתה מגדיר את אורך הקלט

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

 

[גודבאר]

תודה לשניכם נראה לי שהבנתי

אבל ממש תודה!

 

[גודבאר]

עכשיו אפשר לישון