שלום לכולם, הא ניתן לשאול שאלות במבני נתונים?

[DH1212]

שלום לכולם, הא ניתן לשאול שאלות במבני נתונים?

לפחות בצד מתמטי של החומר?17

 

[מכור אנונימי לקולה]

תשאל, מקסימום לא יענו.

 

[DH1212]

אז ככה

נתונה סיבוכיות של שני אלגוריתמים : O1 ו - O2.
צריך להוכיח : O1+O2 = המקסימום מבין שניהם.
כלומר א נתון O וגם נתון O(n^2) אז החיבור בינהם הוא O(n^2 ).
&nbsp
אז ככה:
א. אינטואיטיבית, אכן סיבוכיות של n^2 גדולה יותר מ- n , לדוגמא. אבל מה ההגדרה הפורמלית לגודל של סיבוכיות? איך אפשר להגיד פורמלית שסיבויות אחת גדולה או קטנה מסיבויות אחרת? לפי חלוקה אחד בשני ושאיפה לאין סוף?
ב. כיוונים לאיך להוכיח את זה?

 

[עעעערררר]

א. כן. (או ע"י כפל בקבוע)

ב. נניח בה"כ כי O1 הוא הגדול. אזי מתקיים:
zzz1*O1<=O1+O2<=O1+O1=2*O1
כלומר, היחס בין הסכום ובין המקסימום הוא בין 1 ל-2, ולכן, כסיבוכיויות הם זהים.