בנוגע לסיבוכיות זמן ריצה

[Fat Danken]

בנוגע לסיבוכיות זמן ריצה

אהלן. יש לי שאלה קצרה. אם נתון לי בשאלה מסוימת כי אינדקס המערך הוא בין 1 ל-M, ואני מבצע פעולה בסיבוכיות o כאשר בתוכה יש גם לולאה מ1 עד M (כלומר סריקת המערך), האם הסיבוכיות היא o או o(n^2) ? מורתי אמרה שהסיבוכיות היא o ולא אן בריבוע, מכיוון שכאשר נתון לי את M בשאלה זה כאילו הוא מוגדר כ -const, כלומר כאילו הוא ידוע לי. מה אתם אומרים? תודה [:

 

[lim1989]

אני לא מסכימה עם המורה שלך

לדעתי זה O(n^2)

 

[vinney]

דעתך לא מספיקה

צריך גם הוכחה מתמטית.

 

[ron369]

הסיבוכיות היא או-של M*N, אם הבנתי

נכון את השאלה. תכתוב את זה בבגרות, ותכתוב שבהנתן ש-M קבוע ("אני מניח שהוא קבוע, שכן כך הבנתי את השאלה (המפגרת והלא ברורה שלכם)"), הסיבוכיות היא O(N). איך אתה יודע אם M קבוע? זה תלוי אם הוא נתון כדבר קבוע, שלא תלוי בקלט, או שלא.

 

[Fat Danken]

M באמת אינו תלוי בקלט

נתון היה בשאלה ש-M גודל המערך. רציתי לדעת איך להתייחס אליו, כאל מספר לא ידוע , או כאל מספר קבוע (1). בבחינה עצמה כתבתי או של n*m וע"פ המורה שלי שבדקה את המבחן צדקתי. איך לנהוג בבגרות במקרה שכזה? תודה שוב.

 

[ron369]

איזה גודל של איזה מערך?

 

[gil levi]

אם M לא תלוי בקלט אז הוא O(1) zzz

 

[Fat Danken]

אז סה"כ הסיבוכיות הכוללת היא O

נכון? תודה רבה.

 

[gil levi]

נכון.