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

[niro2003]

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

אם פונקציה מסויימת רצה !n (כלומר n עצרת) פעמים, מה סדר הגודל שלה?

 

[נועה לביא]

O(n!)?

 

[vinney]

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

עצרת זאת פונקציה עם קצב גידול, אתה יכול להשוות אותה לפוקנציות אחרות, ככה אתה יכול לראות שהיא לא בP (קצב גידול של עצרת גדול מקצב גידול של כל פולינום של N). מקדמים לא משנים, זה לא משנה מבחינת קצב הגידול, אם זה עצרת או 5 פעמים עצרת (גבול ההשואה זה קבוע, לכן זה אותה סיבוכיות).

 

[niro2003]

עצרת זה יותר מ(O(n?

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

 

[vinney]

לא ברור לי מה אתה עושה

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

 

[niro2003]

מדובר על פונקציה המוחקת איבר ממערך

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

 

[vinney]

למה להזיז?

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

 

[niro2003]

עלית על הבעיה

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

 

[vinney]

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

תעשה רשימה מקושרת, או מערך אינדקסים.

 

[niro2003]

תוספת

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

 

[דפנה ר]

באופן לא פורמלי הוכחת שהסבוכיות

לינארית ב n

 

[דפנה ר]

אוף איתי צ"ל פולינומיאלית ב n

 

[dp04]

אולי..

לפי מה שהבנתי ממך פונקצית זמן הריצה נראית ככה: n + n-1 + n-2 + n-3 + .. 1 במקרה כזה הסיבוכיות היא O(n^2)

 

[yuvalmadar]

גם לי זה נשמע כך...

 

[niro2003]

אתה צודק

ע"פ הקירוב של סטירלינג זה (O(n^2

 

[yuvalmadar]

:-S

הקירוב של סטירלינג? איך הוא קשור לעניין? פשוט לפי הנוסחא לסכום סדרה חשבונית. קירוב סטירלינג מעריך את n!. (שגדולה אסימפטוטית מכל פולינום, ובפרט לא חסומה על ידי n^2)

 

[dp04]

וגם..

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