סיבוכיות Log N
זמן ריצה ( O (log N. מאיפה זה בא?
אם נסתכל על חיפוש בינרי. אם אנחנו מחפשים x בין N איברים . קודם כל אנחנו נשווה x לאיבר שהוא בעמצא. אם הם שווים - יופי - מחזירים תשובה. אם x קטן מעמצא, נמשיך לחפש שמעולה, אחרת נלך ימינה:
find 10 in { 6, 8, 10, 11, 16, 19, 24,26, 30}
10 == 16 -> smaller
find 10 in { 6, 8, 10,11}
10 == 8 ->bigger
find 10 in {10,11}
10 ==10 return
כל פעם משפר איברים צומצם ל 2.
זמן ריצה יהיה שווה לסה''כ צעדים עד ש N יהיה שווה ל - 1.
N=16
N=8
N=4
N=2
N=1
אנחנו יכולים להסתכל הפוך.
כמה פעמים אנחנו צריכים להכפיל 1 ב 2 עד שנקבל N?
N=1
N=2 // *2
N=4 // *2
N=8 // *2
N=16 // *2
מה זה k במשוואה
2^k = N
זה בדיוק משוואת log!
2^4 = 16 -> log216 = 4
log2N = k -> 2^k = N
בסיס של לוגריתם לא משנה עם אנחנו מדברים על O גדול.
אביגיל פדר
שמשון
אני