Катта Тета
 билан (катта тетеа деб ўқилади) билан f дек тез ўсадиган функциялар синфини белгилаймиз. Расмий нуқтаи назардан ушбу синф юқоридаги икки синфнинг кесишмасини билдиради,
Алгоритмларни солиштиришда бизни ўрганилган алгоритмлардан кўра масалани тез ечувчилари қизиқтиради. Шу туфайли топилган алгоритм ушбу синфга тегишли бўлса у биз учун унча қизиқарли эмас, биз бу синфга тез мурожаат қилмаймиз.
Катта О синфининг тафсилоти
Берилган функцияни  синфга тегишлилигини икки усул билан текшириш мумкин: ё юқорида аниқланган усул билан ёки қуйидагича:
 , если  қандайдир ўзгармас с учун. (1.23)
Бу шуни билдирадики, агар  муносабат мавжуд ва у чексизликдан кичик бўлса, у ҳолда . Айрим функциялар учун бу оддий текшириш эмас. Лопитал қоидасига кўра, бундай ҳолда функцияларни уларнинг кўпайтмалари билан алмаштириш мумкин.
Do'stlaringiz bilan baham: |
