שאלה של יעילות

[Yoava333]

שאלה של יעילות

עשיתי סיבוכיות ל-2 אלגוריתמים, יצא לי שהמקרה הכי גרוע הוא פונקיה אחת הוא:

O = 64 * n * log n​

והמקרה הגרוע של הפונקציה השניה הוא

O = 8 * n^2​

השאלה שלי עד לאיזה ערך של n האלגוריתם השני יהיה יותר מהיר, הלכתי לפי הדרך הבאה:

64 * n * log n = 8 * n^2 /: n != 0 64 * log n = 8 * n log n = n/8​

ואין לי מושג איך אני פותר את השיוויון הזה דרך שניה שניסיתי זה ניסוי וטעיה, והגעתי שב-n = 2 האלגוריתם הראשון יותר איטי מהראשון, למישהו יש מושג איך אני עושה את זה בדרך הראשונה?

 

[orennahum]

דחוף חזרה על חזקות

log a = b ==> a=10^b

 

[Yoava333]

זה לא מאוד עוזר לי...

 

[ron369]

זה כן. אבל באיזה בסיס הלוג?

 

[vinney]

log זה מציין (כמקובל) בסיס 10

בסיס 2 מצוין כlg, בסיס e מצוין כln, לכל שאר הבסיסים מציינים בסיס הלוגריתם בפירוש.

 

[ron369]

אבל ככה זה לא יוצא עגול ../images/Emo13.gif

 

[neko]

כולכם פיספסתם...

LOG זה תמיד בסיס 10, אבל במדמ"ח כותבים בד"כ:

O(log)​

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

 

[shm3]

זה נכון ולא נכון

יש מקומות (אוניברסיטאות) ששם בהגדרה log הוא בבסיס e ולא צריך לציין lan שהרי עיקר הרעיון של log הוא המספר e 1+ 1 \n בחזקת n

 

[vinney]

המם...

אני לא נתקלתי בזה בחיים... גם בכל הספרות המקצועית שראיתי, אם רצו לציין בסיס E - היו משתמשים בLN, וLOG תמיד הניח בסיס 10... שוב, זה עניין של הגדרה, אם יבוא פרופסור ויגיד "LOG מעכשיו תמיד בבסיס E" - זכותו, אבל כמו שאמרתי - מקובל שLOG בלי בסיס מניח בסיס 10, LG מניח בסיס 2 וLN מניח בסיס E.

 

[the new L]

הוא צודק

למשל, כשמתעסקים עם ההרחבה המרוכבת של ln, קוראים לה פשוט Log, וזה תמיד בבסיס e.

 

[ה עוד אחד]

או שקוראים לה ln.

לא נתקלתי עדיין ב LOG כשמתכוונים לבסיס E במרוכבים.

 

[ה עוד אחד]

לא נתקלתי =

או שנתקלתי ואני לא זוכר. אבל בכל מקרה, לא יפה להכליל.

 

[the new L]

פשוט ראיתי

את הסימון הזה בכמה ספרים שונים, אז הנחתי שזה הסטנדרט

 

[orennahum]

ובכן

log n = n/8 8 log n = n n = 10^(n/8) n = (10^(1/8))^n n = 1.3335^n n=1.5722 או n=6.5078

 

[Yoava333]

אתה מוכן להסביר לי איך עשית את

המעבר האחרון מ-

n = a^n​

לתשובה

 

[גיל14]

פתרונות נומריים.

קצת חקירה תראה שיש 3 פתרונות למשוואה הזאת. ניוטון רפסון עם כל מיני נק' התחלתיות תביא לך את שלושת הפתרונות האלה: n = -0.79538422288541333190 (עם 20 ספרות אחרי הנק' כי משעמם לי) n = 1.572313792 (עשר ספרות) n = 6.507099672 (גם עשר ספרות)