שאלה נוספת במבני נתונים
גם יחסית פשוטה, כתבתי את ההוכחה באנגלית כי זה נוח מבחינת היישור.
כמו כן מבני נתונים זה הקורס האקדמאי הראשון שלי, אשמח לשמוע הערות על ההוכחה עצמה:
צ"ל:
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)*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))