עבור לתוכן

מה הסיבוכיות של binarySearch בג'אווה ?

Featured Replies

פורסם

N או LOG2N ?

פורסם
log(n)

פורסם

log2n

פורסם
  • מחבר

log(n)

מה הסיבה בעצם?

הרי מחלקים כל הזמן את המערך ב2 לא?

מה בעצם עושה את זה רק N ?

פורסם

לא מחקלים את זה n פעמים, מחלקים מקסימום log2n פעמים

לכן O(log n)

פורסם

כמובן שאתה צריך למיין את הנתונים לפני כן (בסיבוכיות גדולה יותר).

פורסם

כמובן שאתה צריך למיין את הנתונים לפני כן (בסיבוכיות גדולה יותר).

חיפוש בינארי עושים כשהמערך כבר ממויין .. לרוב המיון של המערך יקח יותר זמן מאשר פשוט להריץ חיפוש לינארי.

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

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

דיונים חדשים