עזרה סכימת מופעים

[ישראלה ישראלי]

@מאה100
נראה לך זה נחשב
@undo
גם אני לא מצליחה להבין
העברתי לכאן כי אני לא יכולה להגיב
זה ב c#

 

[undo]

בעקרון - מה זה משנה מי עושה את העבודה השחורה... הסיבוכיות היא אותה סיבוכיות.

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

O(n)

.
נניח ותעברי עליו בסגנון של חיפוש בינארי - הסיבוכיות תהיה בערך

O(Log n)

.
בכל מקרה - יש לך תלות בגודל המערך, ולכן הסיבוכיות לא תהיה קבועה.

 

[פוטו טופ]

ח ח ח
באיזו שפה אתם מדברות

 

[ישראלה ישראלי]

ח ח ח
באיזו שפה אתם מדברות

C#

 

[this my name]

האם יכול להיות שמתכוונים לימים בחודש?
שאז זה כן קבוע?

 

[undo]

האם יכול להיות שמתכוונים לימים בחודש?
שאז זה כן קבוע?

אבל כמות הקלט משתנה.

 

[this my name]

אבל כמות הקלט משתנה.

אז זה נשמע לא הגיוני,
איך אפשר בסיבוכיות קבועה?

 

[רפ]

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

 

[undo]

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

נכון, אם כי אני מאמינה שאפשר בפחות מ O)N(

 

[משולש ברמודה]

אממ, זה המשך של אשכול אחר?
כי לא כתובה השאלה...

 

[this my name]

נכון, אם כי אני מאמינה שאפשר בפחות מ O)N(

איך אפשר?
את חייבת את כל הנתונים...
זה לא נראה לי כמו חיפוש

 

[שרי רוז]

אהבתי את המילה "סיבוכיות"...

 

[משולש ברמודה]

@ישראלה ישראלי אפשר את השאלה? מעניין אותי...

 

[undo]

איך אפשר?
את חייבת את כל הנתונים...
זה לא נראה לי כמו חיפוש

המערך ממוין.
צריך לחפש את הגבולות בין הערכים השונים.

 

[this my name]

המערך ממוין.
צריך לחפש את הגבולות בין הערכים השונים.

צודקת, לא שמתי לב...

 

[רפ]

נכון, אם כי אני מאמינה שאפשר בפחות מ O)N(

יכול להיות אבל בכל מקרה לא נראה לי אפשרי להגיע לO(log n) מכיון שלא מדובר כאן בחיפוש של ערך יחיד.

 

[this my name]

@ישראלה ישראלי אפשר את השאלה? מעניין אותי...

סכימת מספר מופעים של כל ערך במערך ממוין בסיבוכיות של (o(1

נתון מערך ממוין של אירועים בחודש עבור כל אירוע נתון היום בחודש בו יתקיים יש להחזיר עבור כל יום בחודש כמה אירועים יש בו בסיבוכיות של עד o(1) לדוגמה: 1,1,1,2,4,4... תוצאה 1 - 3 2 - 1 3 - 0 4 - 2 (מספר הימים בחודש ידוע) יש מצב בסיבוכיות כזו?

www.prog.co.il

 

[רפ]

@ישראלה ישראלי האם האלגוריתם אמור להחזיר מספר מופעים עבור יום מסוים?
או להחזיר בבת אחת עבור כל יום בחודש כמה מופעים יש לו?
לא הצלחתי להבין באופן ברור.

 

[undo]

יכול להיות אבל בכל מקרה לא נראה לי אפשרי להגיע לO(log n) מכיון שלא מדובר כאן בחיפוש של ערך יחיד.

אבל מספר החיפושים הוא קבוע (28 - 31)

 

[רפ]

מצאתי כאן משהו:
https://stackoverflow.com/questions/19957753/maintain-a-sorted-array-in-o1
אין לי זמן וסבלנות לקרוא עד הסוף אבל נראה שיש שם פתרון לבעיה.
אם מישהי בכל זאת קוראת ומבינה אשמח לשיתוף.