11-11-2008, 15:38
|
|
|
|
חבר מתאריך: 15.08.06
הודעות: 1,561
|
|
כי logn גדול יותר מקבוע
O(n) אומר שעבור n שהוא גודל הקלט, הסיבוכיות חסומה ע"י קבוע כפול גודל הקלט (הקבוע יכול להיות מיליון, אבל הוא עדיין קבוע).
O(nlogn( אומר דבר דומה. הסיבוכיות חסומה ע"י קבוע כפול גודל הקלט כפול log של גודל הקלט.
לכן, החל מגודל קלט מסוים, nlogn יהיה תמיד גדול מ n (יכול להיות שהנקודה הזאת תהיה כאשר גודל הקלט יהיה מיליארד וחצי, אבל זה לא משנה), ולכן O(nlogn( גדול מ O(n(
מקווה שעזרתי, למרות שזה נראה לי יותר סיבך
_____________________________________
!!אזהרה!!
ההודעה עלולה להכיל שברי אגוזים ו/או איברי דגים כלשהם
!!אזהרה!!
|
ראשי
צ'אט
מצב כלאיים
