Mavzu: Algoritmlar va ma’lumotlarning dastur bilan bog’liqligi Reja


Algoritmlarni tahlil qilishda notatsiya tizimi



Yüklə 0,53 Mb.
səhifə3/13
tarix02.12.2023
ölçüsü0,53 Mb.
#137210
1   2   3   4   5   6   7   8   9   ...   13
4.2-ma\'ruza

Algoritmlarni tahlil qilishda notatsiya tizimi
Algoritmning murakkabligini batafsilroq tahlil qilishda, N uzunlikning bitta kirishida algoritm tomonidan bajarilgan elementar operatsiyalar soni har doim ham bir xil uzunlikning boshqa kiritishida bajarilgan ishlar soni bilan bir xil emasligi ayon bo'ladi. Bu ushbu algoritmning murakkablik funktsiyasining sobit uzunlikdagi ma'lumotlarga xatti-harakatlarini aks ettiruvchi maxsus belgi qo'yish zarurligiga olib keladi.
DA rasmiy tizimda berilgan ushbu vazifaning o'ziga xos muammolarining to'plami bo'lsin. D DA muayyan muammoning vazifasi bo'lsin va | D | = N. Umumiy holda, N kuchining barcha o'ziga xos muammolarini o'z ichiga olgan DA to'plami mavjud:
ushbu to'plamni DN tomonidan belgilang:
DN = {D DN,: |D| = N};
tomonidan o'rnatilgan DN quvvatini belgilang
MDN > MDN = |DN |.
Keyinchalik, mazmunli ravishda, N o'lchovining turli muammolarini echgan holda, ushbu algoritm ba'zi hollarda eng ko'p operatsiyalarni bajaradi, ba'zi holatlarda esa eng kam sonli operatsiyalarni bajaradi. Biz quyidagi belgini olib boramiz:

  1. Fa(N) - N o'lchovining aniq muammolarini hal qilish uchun A algoritmi tomonidan bajariladigan operatsiyalarning eng katta miqdori:

Fa(N) = max {Fa (D)} - eng yomon ish DN

  1. Fa(N) - - eng yaxshi holat - N o'lchovining aniq muammolarini hal qilish uchun A algoritmi tomonidan bajariladigan operatsiyalarning eng kam soni:

Fa(N) = min {Fa (D)} - eng yaxshi holat DN


  1. Yüklə 0,53 Mb.

    Dostları ilə paylaş:
1   2   3   4   5   6   7   8   9   ...   13




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin