Algoritm so`zi va tushunchasi IX asrda yashab ijod etgan buyuk

Goener sxemasi - barcha koeffitsientlar ma'lum bir sohada, masalan, kompleks sonlar sohasida joylashgan ko'phadni binomga bo'lishda to'liq bo'lmagan qism va qoldiqni topish uchun hiyla. Har qanday ko'phad to'liq bo'lmagan qism mavjud bo'lgan shaklda o'ziga xos tarzda ifodalanishi mumkin. Gorner sxemasi (yoki Gorner qoidasi, Gorner usuli) oʻzgaruvchining berilgan qiymati uchunmonomlar yigʻindisi sifatida yoziladigan koʻphadning qiymatini hisoblash algoritmidir. Horner usuli polinomning ildizlarini topish, shuningdek hosilalarini hisoblash imkonini beradi
Gorner sxemasining umumiy formulasini chiqarish.
Qolgan qismi bilan polinomini binomialga bo'lish polinomini va bo'ladigan r sonini topishni anglatadi.
Keling, bu tenglikni batafsil yozaylik:

Keling, koeffitsientlarni bir xil darajada tenglashtiraylik:


ko`phadni ikkihadga bo`lishdagi qoldiqni hisoblashning Gorner (Xorner Uilyam (1786-1837) – ingliz matematigi) sxemasi deb ataluvchi usulini ko`rsatamiz.

bo`lsin. Bunda
(1) da x ning bir xil darajalari oldidagi koeffitsiyentlarni tenglashtirib quyidagiga ega bo`lamiz:
_-1
Bundan ko`rinadiki,
Bo`linma va qoldiqni hisoblash quyidagi jadval yordamida topiladi.

				...
				...
				...

5.Algoritmlarni eng yomon va o’rtacha xolatlarda baholash

Algoritmni buyurtma qilishning murakkabligini baholash algoritmlar murakkabligining yuqori chegarasidir. Agar dastur katta murakkablik darajasiga ega bo'lsa, bu algoritm haqiqatan ham uzoq davom etadi degani emas. Ba'zi bir ma'lumot to'plamlarida, algoritmni bajarilishi ularning murakkabligi asosida taxmin qilishdan ancha kam vaqt talab etadi. Masalan, A vektorda berilgan elementni qidiradigan kodni ko'rib chiqing. Agar kerakli element ro'yxatning oxirida bo'lsa, unda dastur N bosqichni bajarishi kerak bo'ladi. Bunday holda, algoritmning murakkabligi O (N) dir. Ushbu eng yomon holatda, algoritmning ishlash vaqti maksimal bo'ladi. Boshqa tomondan, kerakli narsa birinchi holatda ro'yxatda bo'lishi mumkin. Algoritm faqat bitta qadamni bajarishi kerak. Bunday holat eng yaxshi deb nomlanadi va uning murakkabligi O (1) deb baholanishi mumkin.

function Locate(data: integer): integer;
var i:
integer;
fl:
boolean;
begin
fl:=false;
i:=1;
while (not fl) and (i<=N) do
begin
if A[i]=data then
fl:=true else
i:=i+1;
end;
if not fl then
i:=0;
Locate:=I;
end;
Ushbu ikkala holat ham mumkin emas. Bizni kutilgan variant ko'proq qiziqtiradi. Agar ro'yxat elementi dastlab tasodifiy aralashtirilsa, unda kerakli element ro'yxatning istalgan joyida paydo bo'lishi mumkin. O'rtacha, kerakli elementni topish uchun N / 2 taqqoslash talab qilinadi. Shunday qilib, ushbu algoritmning murakkabligi o'rtacha O (N / 2) = O (N).
Bunday holda, o'rtacha va kutilgan murakkablik bir xil, ammo ko'plab algoritmlar uchun eng yomon holat kutilganidan juda farq qiladi. Masalan, eng yomon holatlarda tez tartiblash algoritmi O (N ^ 2) tartibining murakkabligiga ega, kutilayotgan xattiharakatlar esa O (N * log (N)) bahosi bilan tavsiflanadi, bu ancha tezroq

6. Algoritmlarni tasvirlash usullari