#pragma argsused #include #pragma hdrstop #include

Asimptotik tahlilning asosiy xususiyatlari

• Tranzitivlik (O'tkazuvchanlik): f (n) = Θ (g (n)) va g (n) = Θ (h (n)) ⇒ f (n) = Θ (h (n)). Bu shuningdek, O va Ω baholari uchun ham amal qiladi.

• Refleksivlik : f (n) = Θ (f (n)). Xuddi shunday O va Ω uchun.

• Simmetriklik: agar f(n) = Θ(g (n)) bo’lib, g (n) = Θ(f (n)) bo'lsa.

 • Simmetriya transpozitsiyasi: agar  f (n) = O (g (n)) bo’lib, g (n) = Ω (f (n)) bo'lsa.

• Agar f (n) har qanday doimiy k> 0 uchun O ( kg (n)) da joylashgan bo'lsa, u holda f (n) O (g (n)) da joylasadi.

• Agar f1(n), O (g1 (n)) da joylashgan va f2 (n), O (g2 (n)) da joylasgan bo'lsa, u holda (f1 + f2) (n), O ( max (g1 (n) )) , (g1 (n))) da joylashadi. 

• Agar f1 (n), O (g1 (n)) da joylashgan va f2 (n), O (g2 (n)) da joylashgan bo'lsa, u holda f1 (n) f2 (n), O (g1 (n) g1 (n) da )) da joylashadi.