Bog'liq 5-Ma’ruza. Algoritmlar samaradorligini baholash
Mashaqqatlilik funksiyasidan kelib chiqqan holda algoritmlarning murakkablik sinflari 1-jadval f(n) ko’rinishi Algoritmlar sinfining xarakteristikasi 1 Ko’plab instruksiyalarda ko’plab funksiyalar bir yoki bir necha
marotaba ishga tushiriladi. Agar dasturning barcha instruksiyasi
shunday xususiyatga ega bo’lsa, u holda dasturning bajarilish
vaqti doimiy.
log N Dasturning bajarilish vaqti logarifmik bo’lsa, N ning ortishi bilan
dastur sekinlashadi. Bunday bajarilish vaqti odatda katta
masalani har bir qadamda qandaydir doimiy faktorga
kamaytirgan holda kichikroq qismmasalalar jamlanmasi shaklida
ifodalovchi dasturlarga xos. Unchalik katta bo’lmagan konstanta
kattaligida bajarilish vaqtini ko’rib chiqamiz. Asosning
o’zgarishi logarifm qiymatining o’zgarishiga sezilarli ta’sir
ko’rsatmaydi: agar asos yoki tartib 10 ga teng bo’lsa, u holda
N=1000 bo’lganda log N = 3 bo’ladi; N=1 000 000 bo’lganda log
N ning qiymati ikki barabar oshadi. Parametr qiymatining
ikkilanishi bilan log N doimiy kattalikka o’sdi, N parametr N
2
ga
yetganda esa bajarilish vaqti ikkilanishi mumkin.
N Dastur bajarilish vaqti chiziqli bo’lsa, bu odatda har bir kiruvchi
element biroz qayta ishlashi lozimligini anglatadi. N millionga
teng bo’lganda uning bajarilish vaqti ham aynan shunga teng
bo’ladi. N ikkilanganda bajarilish vaqti ham ikkilanadi. Bu N
kirishlarni qayta ishlash (yoki N chiqishni amalga oshirish)
algoritmlari uchun optimal holat hisoblanadi.
N log N N log N ga proporsional bajarilish vaqti shunday hollarda hosil
bo’ladiki, bunda algoritm masalani yechishda uni kichikroq
qismmasalalarga bo’lib, ularni mustaqil yechib keyin
yechimlarni birlashtiradi. Bunday algoritmning bajarilish vaqti N
log N ga teng. N=1 000 00 ga teng bo’lganda, ga
