Zeydel usulining mohiyati.
A matritsaning diagonal elementlari noldan farqli
bo’lsin i=1,2,3,…,n. Sistemaning
birinchi tenglamasini x
1
ga, ikkinchi
tenglamasini x
2
ga va hokazo n – tenglamasini x
n
ga nisbatan yechib,
(4)
sistemaga
ega
bo’lamiz,
bu
yerda
Zeydel usuli
ketma – ket yaqinlashish usulining boshqacha ko’rinishi bo’lib, unda
(k+1) – yaqinlashishni hisoblashda yangi topilgan x
1
,x
2
,...., x
k
noma’lumning
(k+1)-yaqinlashishi (iteratsiya usulida k– yaqinlashish) e’tiborga olinadi.
x
i
noma’lumning k – yaqinlashishi ma’lum bo’lsin, u holda (k+1) – yaqinlashish
quyidagi
formula
bilan
topiladi.
Argar keltirilgan (4)
sistema uchun
; i,j=1,2,3,…n. shartlarning birortasi o’rinli
bo’lsa Boshlang’ich yaqinlashish qanday tanlanishidan qat’iy nazar tenglamalar
sistemasi yagona yechimga yaqinlashadi. (1)sistema uchun iteratsiya usulida
yaqinlashish sharti
tartibli ta chiziqli algebraik tenglamalar sistemasining ko’rinishi quyidagi
ifodadan iiborat:
(1)
Bu yerda lar ma’lum sonlardan iborat bo’lib, noma’lumlarning
Masalan:
Quyidagi tenglamalar
sistemasining yechimini
aniqlikda topish talab etilsin.
Tenglamalar sistemasini yechish uchun quyidagi amallarni bajaramiz.
1. SHartni tekshiramiz,ya’ni
2. Shart bajarilayapti demak tenglamalar sistemasini Zeydel usulida
yechimni topish mumkin.
3. Tenglamalar
sistemasini mos ravishda x
1
, x
2
,x
3
noma’lumlarga nisbatan
yechamiz:
4.k=0 deb birinchi yaqinlashishni aniqlaymiz.
5.k=1 deb ikkinchi yaqinlashishni aniqlaymiz:
6. Yaqinlashish shartini tekshiramiz:
Topilgan yechim berilgan aniqlikni qanoatlantirmayapti shuning uchun
jarayonni davom ettiramiz.
7.k=3 deb uchunchi yaqinlashishni aniqlaymiz:
8. Yaqinlashish shartini tekshiramiz:
Topilgan yechim berilgan aniqlikni qanoatlantiryapti. Demak tenglamalar
sistemasining taqribiy yechimi: x
1=
0.3618; x
2
=0.1481; x
3
=-0.4743 ekan.
O'z joyida birlashtirish tartibi, O ( n jurnal 2 n)
•
Tez tartiblash
, O ( n jurnal n), ehtimolli versiyada eng yomon holatda
chiziqli-logarifmik bajarilish vaqti mavjud. Mumkin bo'lmagan versiyada
o'rtacha qiyinchilikni o'lchash uchun chiziqli jurnalning ishlash vaqti
mavjud.
• Uyumni tanlash, O ( n jurnal n), birlashma tartiblash, introsort, ikkilik
daraxt tartibi, silliq tartiblash, solitaire turi, va hokazo. eng yomoni
• Tez Furye o'zgarishi, O ( n jurnal n)
• Monge matritsalarini hisoblash, O ( n jurnal n)
Chiziqli logarifmik vaqt
Chiziqli-logarifmik - bu ko'rsatkichli kvazizikli vaqtning maxsus holati k= 1
logarifmik hadda.
Chiziqli logarifmik funktsiya shaklning funktsiyasidir n jurnal n(masalan,
mahsulot chiziqli va logarifmik atamalar). Algoritm ishlashi aytiladi
chiziqli-logarifmik vaqt, agar T(n) = O ( n jurnal n) ... Shunday qilib,
chiziqli-logarifmik element chiziqli haddan tezroq, lekin har qanday
polinomga qaraganda sekinroq o'sadi. n 1 dan qat'iy yuqori darajaga ega.
Ko'p hollarda ish vaqti n jurnal n oddiygina operatsiya natijasidir t (log n) n
bir marta. Masalan, ikkilik daraxt bilan tartiblash har bir elementni n
o‘lchamli massivga birma-bir kiritish orqali ikkilik daraxt hosil qiladi. Insert
operatsiyasidan beri muvozanatli ikkilik qidiruv daraxti O ni oladi (log n),
algoritmning umumiy bajarilish vaqti chiziqli-logarifmik bo'ladi.
Taqqoslash bo'yicha saralash hech bo'lmaganda logdan beri eng yomon
holatlardagi taqqoslashlarning chiziqli jurnalini talab qiladi ( n!) = Θ( n
jurnal n) Stirling formulasi bo'yicha. Xuddi shu bajarilish vaqti ko'pincha
takrorlanish tenglamasidan kelib chiqadi T(n) = 2 T(n/ 2) + O ( n)
Har qanday dasturchi uchun algoritmlar nazariyasining asoslarini
bilish juda muhim, chunki algoritmlarning umumiy xususiyatlarini
va ularni namoyish etish uchun rasmiy modellarni o'rganadigan
fan. Hatto informatika darslaridan bizga kelajakda maktabga
qaraganda murakkabroq topshiriqlarni yozishda yordam beradigan
oqim jadvallarini tuzishga o'rgatiladi.
Hech kimga sir emaski
,
deyarli har doim ma'lum bir muammoni hal qilishning bir necha
yo'li mavjud: kimdir ko'p vaqt sarflashni, boshqalari resurslarni
sarflashni o'z ichiga oladi, boshqalari esa deyarli echim topishga
yordam beradi.
Siz har doim vazifaga muvofiq, xususan, muammolar sinfini hal
qilish algoritmlarini ishlab chiqishda eng maqbul variantni
izlashingiz kerak.
Shuningdek
, algoritm turli xil hajmlar va
miqdorlarning boshlang'ich qiymatlarida o'zini qanday tutishi,
unga qanday resurslar kerakligi va yakuniy natijani olish uchun
qancha vaqt kerakligini baholash ham muhimdir.
Algoritm tushunchasi va uning ta’rifi.
Ma'lumotni qayta ishlash algoritmi - bu kompyuter fanida
muammoni hal qilish usulining tavsifi bo'lib, uni keyinchalik
tanlangan dasturlash muhitida amalga oshirish mumkin.
Algoritmni tahlil qilish - bu baholashni o'rganadigan informatika
sohasidirishlash algoritmlari .
Algoritmning murakkabligi bu algoritmni tahlil qilishda hisobga
olinadigan elementar operatsiyalar sonidir.
A algoritmi bilan belgilangan operatsiyalarning eng ko'p soni
og'irlikning eng yomon holati bo'lib , u ma'lum bir o'lchovdagi D
kirishlarni kiritadi .
Laboriousness eng yaxshi ishi algoritm operatsiyalar kichik soni A
barcha yozuvlari da bir D ma'lum o'lchov n .
Laboriousness o'rtacha ishi algoritm operatsiyalar o'rtacha soni A
barcha yozuvlari da bir D ma'lum o'lchov n .
Algoritmning murakkabligi funktsiyasi - algoritmning
murakkabligi bu D kirishidagi A parametr parametrlariga
bog'liqligi .
Algoritmning vaqt murakkabligi eng yomon holatga algoritmning
murakkablik funktsiyasini asimptotik baholashdir.
Xotira hajmi - D kirish uchun A algoritmini amalga oshirishda
ishtirok etadigan xotira joylarining maksimal soni .
Algoritmning kapasitiv murakkabligi bu algoritmning eng yomon
holatdagi xotira funktsiyasini asimptotik baholashdir.
Algoritmning
eng yomon
, o'rta va eng yaxshi holatlaridagi
resurslarning murakkabligi vaqt va funktsiyalar sinflarining
tartiblangan juftligi.asemptomatik belgi bilan aniqlanadigan va
ko'rib chiqilayotgan holatga mos keladigan sig'im murakkabligi .
Ma'lumotlar tuzilmalari bilan ishlash algoritmlari bu olinadigan
asosiy tamoyillar va metodologiyani aniqlaydigan
algoritmlardirma'lumotlarni qayta ishlash usullarini tushunish .
Saralash algoritmlari massivlar va fayllarni tartibga solish uchun
mo'ljallangan algoritmlardir.
Qidiruv algoritmlari bu katta ma'lumotlar to'plamida ma'lum
elementlarni qidirish uchun mo'ljallangan algoritmlar.
Graf algoritmlari bu amalga oshirish uchun mo'ljallangan
algoritmlardirgrafik ayirish va qidirish strategiyalari .
Simlarni qayta ishlash algoritmlari bu belgilar ketma-ketligini
qayta ishlash uchun bir qator usullarni o'z ichiga olgan
algoritmlardir.
Geometrik algoritmlar bu geometrik ob'ektlardan foydalangan
holda muammolarni echish uchun algoritmlardir.
Algoritmni baholash
Algoritmning murakkabligini o'lchashning bir necha usullari
mavjud. Dasturchilar odatda algoritm tezligiga e'tibor qaratishadi,
ammo boshqa ko'rsatkichlar ham bir xil ahamiyatga ega - xotira
hajmiga, diskdagi bo'sh joyga talablar. Tez algoritmdan
foydalanish, agar kompyuter ishlashi kerak bo'lganidan ko'proq
xotirani talab qilsa, kutilgan natijalarga olib kelmaydi.
Xotira
yoki vaqt
Ko'pgina algoritmlar xotira hajmi va tezligi o'rtasida tanlovni taklif
qiladi. Muammoni tezroq, katta hajmdagi xotiradan foydalangan
holda yoki ozroq hajmni olib, sekinroq hal qilish mumkin. Bu
holatda odatiy misol eng qisqa yo'llarni qidirish algoritmi
hisoblanadi. Tarmoq shaklida shahar xaritasini taqdim etib, siz
ushbu tarmoqning har qanday ikkita nuqtasi orasidagi eng qisqa
masofani aniqlash uchun algoritm yozishingiz mumkin. Bu
masofalarni kerak bo'lganda hisoblamaslik uchun barcha nuqtalar
orasidagi eng qisqa masofani ko'rsatib, natijalarni jadvalga
saqlashimiz mumkin. Berilgan ikkita nuqta orasidagi eng qisqa
masofani aniqlashimiz kerak bo'lsa, biz shunchaki jadvalning
tugagan masofasini olishimiz mumkin. Natija bir zumda olinadi,
ammo bu juda katta hajmdagi xotirani talab qiladi. Katta shahar
xaritasida o'n minglab fikrlar bo'lishi mumkin. Keyin, yuqorida
tavsiflangan jadvalda 10 milliarddan ortiq hujayralar bo'lishi kerak.
Bular Algoritmning ishlashini yaxshilash uchun qo'shimcha 10 Gb
xotirani ishlatish kerak. Ushbu qaramlikdan kosmik-vaqt
murakkabligi g'oyasi kelib chiqadi. Ushbu yondashuv bilan,
algoritm bajarilish tezligi va iste'mol qilinadigan xotira nuqtai
nazaridan baholanadi. Vaqtinchalik murakkablikka
e'tiborni
qaratamiz
, ammo shunga qaramay, biz iste'mol qilingan
xotiraning hajmini aniq belgilaymiz.
Buyurtmani baholash
Turli xil algoritmlarni taqqoslashda ularning murakkabligi kirish
ma'lumotlari miqdoriga bog'liqligini bilish muhimdir. Masalan,
bitta usul yordamida saralashda ming sonlarni qayta ishlash 1 s.,
Va million sonlarni qayta ishlash uchun 10 s vaqt kerak bo'ladi,
boshqa algoritmdan foydalanish esa 2 s vaqtni talab qilishi
mumkin. va 5 s. navbati bilan Bunday sharoitda qaysi algoritm
yaxshiroq ekanligini aniq aytish mumkin emas. Umumiy holda,
algoritmning murakkabligini kattalik tartibida baholash mumkin.
Agar kirish ma'lumotlarining o'lchamlari oshgani sayin,
algoritmning bajarilish vaqti f (N) funktsiyasi bilan bir xil tezlikda
oshsa, algoritmda O (f (n)) murakkablik bor. A [NxN] matritsasi
uchun har bir satrda maksimal elementni topadigan kodni ko'rib
chiqing.
for i:=1 to N do
begin
max:=A[i,1];
for j:=1 to N do
begin
if A[i,j]>max then
max:=A[i,j]
end;
writeln(max);
end;
Ushbu algoritmda i o'zgaruvchisi 1 dan N.gacha o'zgaradi, i ning
har bir o'zgarishi
bilan birga
, j o'zgaruvchisi ham 1 dan N ga
o'zgaradi. Tashqi aylanishning har bir N takrorlanishida ichki
pastadir ham N marta bajariladi. Ichki pastadir takrorlanishlarining
umumiy soni N * N dir. Bu O (N ^ 2) algoritmining
murakkabligini aniqlaydi. Algoritmning murakkablik tartibini
taxmin qilishda faqat eng tez o'sadigan qismdan foydalanish kerak.
Vazifalar aylanishi N ^ 3 + N ifodasi bilan tasvirlangan deb taxmin
qiling. Bunday holda, uning murakkabligi O ga teng bo'ladi (N ^
3). Funktsiyaning tez o'sib boruvchi qismini ko'rib chiqish,
algoritmning xatti-harakatlarini N.ning ortishi bilan baholashga
imkon beradi. Masalan, N = 100 bilan N ^ 3 + N = 1000100 va N
= 1000000 o'rtasidagi farq atigi 100 ga teng, bu 0,01%. O ni
hisoblashda, ifodalarda doimiy omillarga e'tibor bermaslik
mumkin. 3N ^ 3 ish bosqichiga ega bo'lgan algoritm O (N ^ 3) deb
hisoblanadi. Bu O (N) nisbati muammoning hajmiga bog'liqligini
yanada aniqroq qiladi.
Qiyinchilikni aniqlash
Dasturning eng murakkab qismlari odatda pastadir va qo'ng'iroq
qilish protseduralari. Oldingi misolda butun algoritm ikki tsikl
yordamida amalga oshirildi. Agar bitta protsedura boshqasini
chaqirsa, u holda protseduraning murakkabligini batafsilroq
baholash kerak. Agar unda muayyan miqdordagi ko'rsatmalar
bajarilgan bo'lsa (masalan, bosib chiqarish), unda bu
murakkablikni baholashga deyarli ta'sir qilmaydi. Agar O (N)
bosqichlar chaqirilayotgan protsedurada bajarilsa, funktsiya
algoritmni sezilarli darajada murakkablashtirishi mumkin. Agar
protsedura ko'chadan
ichkarisiga chaqirilsa
, u holda ta'sir yanada
katta bo'lishi mumkin. Misol tariqasida ikkita protsedurani ko'rib
chiqing: O (N ^ 3) murakkabligi bilan sekin va O (N ^ 2)
murakkabligi bilan.
procedure Slow;
var i,j,k: integer;
begin
for i:=1 to N do
for j:=1 to N do
for k:=1 to N do
какое-то действие}
end;
procedure Fast;
var
i,j: integer;
begin
for i:=1 to N do
for j:=1 to N do
Slow;
end;
procedure Both;
begin
Fast;
end;
Algoritm murakkabligining asosiy ko'rsatkichi muammoni hal
qilish uchun zarur bo'lgan vaqt va talab qilinadigan xotira miqdori
hisoblanadi. Shuningdek, topshiriqlar sinfi uchun murakkablikni
tahlil qilganda ma'lum bir ma'lumotni - kirish hajmini tavsiflovchi
ma'lum bir raqam aniqlanadi . Shunday qilib, algoritmning
murakkabligi kirish hajmining funktsiyasi degan xulosaga
kelishimiz mumkin.
Algoritmning murakkabligi bir xil kirish hajmi bilan farq qilishi
mumkin, ammo har xil kirish ma'lumotlari. Eng yomon , o'rta yoki
eng yaxshi holatda murakkablik tushunchalari mavjud . Odatda,
eng yomon ishning murakkabligi baholanadi. Vaqtning
murakkabligi eng yomon holatda, berilgan o'lchamdagi masalani
echishda algoritmni bajarish paytida bajariladigan
operatsiyalarning maksimal soniga teng bo'lgan kirish hajmining
funktsiyasi. Eng yomon holatda, kapasitiv murakkablik bu
o'lchamdagi muammolarni echishda foydalanilgan xotira
hujayralarining maksimal soniga teng kirish hajmi funktsiyasidir.
Algoritmni o'sish
tartibi
Murakkablikning o'sishi tartibi (yoki aksiomatik murakkablik)
katta kirish o'lchamiga ega bo'lgan algoritmning murakkablik
funktsiyasining taxminiy xatti-harakatlarini tavsiflaydi. Bundan
kelib chiqadiki, vaqtning murakkabligini baholashda elementar
operatsiyalarni ko'rib chiqishga hojat yo'q, algoritmning
bosqichlarini ko'rib chiqish kifoya qiladi.
Algoritmning bosqichi bu ketma-ket joylashgan elementar
operatsiyalar to'plami bo'lib, ularning bajarilish vaqti kirish
hajmiga bog'liq emas, ya'ni u yuqorida qandaydir doimiy bilan
chegaralangan.
Asimptotik baholash turlar
O - eng yomon holat
F (n)> 0 murakkabligini , g (n)> 0 tartibidagi funktsiyani , kirish
o'lchamini n> 0 ko'rib chiqing . Agar f (n) = O (g (n)) va o'zgarmas
kattaliklar ham bor c> 0 , n 0 > 0 , keyin 0 n 0 .
Bu holda g (n) funktsiya f (n) ning asemptomatik ravishda aniq
qiymatidir. Agar f (n) algoritmning murakkabligi funktsiyasi
bo'lsa, unda murakkablik tartibi f (n) - O (g (n)) deb belgilanadi.
Bu ibora g (n) dan doimiy omilgacha tez o'smaydigan funktsiyalar
sinfini belgilaydi.
Θ - o'rtacha
ish uchun ball
Ta'kidlash joizki, n> n 0 uchun f (n) funktsiya hamma joyda c 1 *
g (n) va c 2 * g (n) orasida bo'ladi , bu erda c doimiy omil.
Masalan, f (n) = n 2 + n bilan ; g (n) = n 2 .
Algoritm murakkabligining statik va dinamik o‘lchovlari. Xotirayokivaqt.
Foydalanilgan adabiyotlar:
1
ALGORITMLASH VA DASTURLASH ASOSLARI Azamatov A.R.
2
Гуломов С.С. ва бошқалар. Ахборот тизимлари ва технологиялари.
Тошкент,2000
3
Virt N.. Algoritmy i struktury dannyx. – Dossa, Xamarayan, 1997.
4
student.tuitkf.uz
saytiAlgoritmlarniloyihalashfanidaberilgandarsmateriallari.
|
