שאלה נוספת במבני נתונים

[DH1212]

שאלה נוספת במבני נתונים

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

צ"ל:
O(f)*O(g) = O(f*g)
O(f) means that there is x1 , c1 so
f(x) <= c1*O(f(x))
for every >=x1

O(g) means that there is x2,c2 so
g(x)<=c2*O(g(x))
for every x>=x2

the product O(f)*O(g) means that
f(x)*g(x) <= c1*O(f(x))*c2*O(g(x)) for every x >= x1,x2
Assign c3 = c1*c2 And x3 >= Max(x1,x2)
And we get:
f(x)*g(x) <= c3*O(f(x))O(g(x)) for every x >= x3

O(f*g) means that there is x4 , c4 so
f(x)*g(x) <= c4* O(f(x)*g(x)) for every x>=x4

let's choose x5 = Max (x3,x4) and c5 = Max(c3,c4)
and we'll get for both:
f(x)*g(x) <= c5*O(f(x))O(g(x)) for every x >= x5
f(x)*g(x) <= c5* O(f(x)*g(x)) for every x>=x5

meaning O(f(x))O(g(x)) = O(f(x)*g(x))

​

 

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

הערות.

השורות
O(f) means that there is x1 , c1 so
f(x) <= c1*O(f(x))
הן חסרות משמעות ולא נכונות. O(f) זאת פשוט קבוצה של פונקציות. השורה השניה לא הגיונית כי אתה משתמש בO(f) כדי להגדיר מה זה O(f).
הדרך להוכיח את הטענה שלך זה לכחת פונקציות כלליות מהקבוצות בצד שמאל של המשוואה, ולהראות שהן שייכות גם לצד הימני, או פורמלית:
אם הפונקציות f,g,h,k מקיימות f=O(g), h=O(k), צ"ל: מתקיים f*h=O(g*k), ומפה לעבוד לפי ההגדרות.

 

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

ודרך אגב,

איך זה הקורס הראשון שאתה עושה? בד"כ הוא דורש ערימה של קדמים.

 

[DH1212]

לא נרשמתי לתואר

אני מתכנת במקצוע ורציתי להשלים קצת חסרים תיאורתים , נרשמתי רק לקורס הזה

 

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

*לקחת.

 

[DH1212]

ניסיון שני

צ"ל:
O(f)*O(g) = O(f*g)
&nbsp
Let h(x) = O(f)*O(g)
So there is c1 , x1 so
c1*h(x)>= O(f(x))*O(g(x))
for every x>x1
&nbsp
let k(x) = O(f*g)
So there is c2 , x2 so
c2*k(x)>=O(f(x)*g(x))
for every x>x2
&nbsp
we have
c1*h(x)>= O(f(x))*O(g(x)) for every x>x1
c2*k(x)>=O(f(x)*g(x)) for every x>x2
let’s choose x3=max(x1,x2) and c3=max(c1,c2)
so
c3*h(x)>= O(f(x))*O(g(x)) for every x>x3
c3*k(x)>=O(f(x)*g(x)) for every x>x3
meaning h(x)=k(x)
&nbsp

 

[DH1212]

הקפצה?

 

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

שוב,

O(f(x)) זאת קבוצה, אז השורה
c1*h(x)>= O(f(x))*O(g(x)) היא חסרת משמעות.
מה אומרת ההגדרה? אם k(x) = O(f*g), אז קיימים c,x0 כך ש k(x) <= c*f(x)*g(x) לכל x>x0 (שוב, שים לב שאם מגדירים מה זה O(f*g), לא הגיוני שO(f*g) יהיה בהגדרה).

 

[DH1212]

צודק..

אז אם הייתי מחליף את O(f(x))*O(g(x)) ב- k(x) <= c*f(x)*g(x) וכנ"ל שאר השורות הרלוונטיות - זו היה נכון?
ואיך אומרים באנגלית "מקיים"?

 

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

לא, למשל המסכנה הסופית היא גם לא נכונה. תתחיל מהתחלה.