Асимптотик тооцоо. Тооцооллын нарийн төвөгтэй байдлын асимптотик тооцоо. Алгоритмын асимптотик үнэлгээ
Их хэмжээний оролтын өгөгдөл бүхий тодорхой асуудлын жишээг шийдвэрлэхийн тулд гүйцэтгэсэн алгоритмуудын цаг хугацааны зардлыг харьцуулах шинжилгээг гэнэ. асимптотик. Асимптотын төвөг багатай алгоритм нь хамгийн үр дүнтэй байдаг.
Асимптотик шинжилгээнд алгоритмын нарийн төвөгтэй байдалнь өгөгдлийн хэмжээ ихсэх тусам алгоритмын ажиллах хугацаа хэр хурдан нэмэгдэж байгааг тодорхойлох боломжийг олгодог функц юм.
Асимптотик шинжилгээнд олсон өсөлтийн гол тооцоонууд нь:
- Ο (O-том) – цагийн функцийн өсөлтийн дээд асимптотик тооцоо;
- Ω (Омега) – цагийн функцийн өсөлтийн бага асимптотик тооцоо;
- Θ (Тета) – цагийн функцийн өсөлтийн доод ба дээд асимптотик тооцоо.
Болъё n- өгөгдлийн хэмжээ. Дараа нь алгоритмын функцийн өсөлт е(n) та функцуудыг хязгаарлаж болно g(n) асимптотоор:
Жишээлбэл, өрөөг цэвэрлэх хугацаа нь тухайн өрөөний талбайгаас шугаман хамааралтай байдаг (Θ( С)), өөрөөр хэлбэл, талбайн хэмжээ нэмэгдэж байна nудаад цэвэрлэх хугацаа мөн нэмэгдэнэ nнэг удаа. Утасны дэвтэрээс нэр хайхад шугаман хугацаа шаардагдана Ο (n), хэрэв та шугаман хайлтын алгоритм, эсвэл бичлэгийн тооноос логарифмын хувьд хамаарах хугацаа ( Ο (лог 2 ( n))), хоёртын хайлт ашиглах тохиолдолд.
Бидний хамгийн их сонирхдог зүйл Ο - функц. Түүнээс гадна, дараагийн бүлгүүдэд алгоритмын нарийн төвөгтэй байдлыг зөвхөн асимптотын дээд хязгаарт өгөх болно.
"Алгоритмын нарийн төвөгтэй байдал" гэсэн хэллэгийн дор Ο (е(n))" гэдэг нь оролтын өгөгдлийн хэмжээ ихсэх тусам гэсэн үг юм n, алгоритмын ажиллах хугацаа зарим тогтмолыг үржүүлснээс илүү хурдан өсөхгүй е(n).
Асимптотик шинжилгээний чухал дүрмүүд:
- О(к*е) = О(е) – тогтмол хүчин зүйл к(тогтмол) нь өгөгдлийн хэмжээ ихсэх тусам утга нь алдагдах тул хасагдана, жишээлбэл:
O(9,1n) = O(n)
- О(е*g) = О(е)*О(g) – хоёр функцийн үржвэрийн нарийн төвөгтэй байдлын тооцоо нь тэдгээрийн нарийн төвөгтэй байдлын үржвэртэй тэнцүү байна, жишээлбэл:
O(5n*n) = O(5n)*O(n) = O(n)*O(n) = O(n*n) = O(n 2)
- О(е/g)=О(е)/О(g) – хоёр функцийн нарийн төвөгтэй байдлын тооцоо нь тэдгээрийн нарийн төвөгтэй байдлын коэффициенттэй тэнцүү байна, жишээлбэл:
O(5n/n) = O(5n)/O(n) = O(n)/O(n) = O(n/n) = O(1)
- О(е+g) давамгайлсантай тэнцүү байна О(е) Мөн О(g) – функцүүдийн нийлбэрийн нарийн төвөгтэй байдлын тооцоог эхний болон хоёр дахь нөхцлийн давамгайлагчийн нарийн төвөгтэй байдлын тооцоогоор тодорхойлно, жишээлбэл:
O(n 5 +n 10) = O(n 10)
Үйлдлийн тоог тоолох нь уйтгартай бөгөөд хамгийн чухал нь огт шаардлагагүй юм. Дээр дурдсан дүрмүүд дээр үндэслэн алгоритмын нарийн төвөгтэй байдлыг тодорхойлохын тулд бидний өмнөх шиг бүх үйлдлүүдийг тоолох шаардлагагүй бөгөөд тодорхой алгоритмын загвар (оператор эсвэл операторын бүлэг) ямар нарийн төвөгтэй болохыг мэдэхэд хангалттай. байна. Тиймээс гогцоо, рекурс агуулаагүй алгоритм нь байнгын төвөгтэй байдаг О(1). Гогцоог гүйцэтгэх нарийн төвөгтэй байдал nдавталт нь тэнцүү байна О(n). Ижил хувьсагчаас хамааран хоёр үүрлэсэн гогцоо барих n, квадрат нарийн төвөгтэй байдаг О(n 2).
Онолын шинжилгээний хувьд хамгийн чухал зүйл бол гүйцэтгэлийн хугацаа нь оролтын өгөгдлийн тооноос хамааралтай болохыг тодорхойлдог тусгай функц биш, харин том N-ийн хувьд түүний өсөлтийн дараалал чухал юм. Хэмжилт хийх нь илүү тохиромжтой сонгосон оролтын өгөгдлийн багц дээр даалгаврыг гүйцэтгэхэд шаардагдах тодорхой хугацааны тооцоо. Гол асуудлууд нь нэгдүгээрт, зарчмын хувьд хязгаарлагдмал хүлээн зөвшөөрөгдсөн хугацаанд компьютерийн шийдлийн боломжийг тодорхойлох, хоёрдугаарт, альтернатив хувилбаруудыг харьцуулах, зохисгүй алгоритмуудыг бүрэн хүчин чармайлт гаргахаас өмнө авч үзэхээс татгалзах явдал юм. хэрэгжилт.
Өөрөөр хэлбэл, шийдвэрлэх үүрэг гүйцэтгэдэг асимптотик тооцооалгоритмын тооцооллын нарийн төвөгтэй байдал. Бөмбөлөг эрэмбэлэх алгоритмын хувьд дээр дурдсан хамаарлаас хязгаарыг авч үзье, оролтын өгөгдлийн тоо N хязгааргүй байх хандлагатай байна:
Ахиу үнэлгээнд дээд зэрэглэлүүд давамгайлдаг тул доод зэрэглэлийг хасдаг. Тиймээс хөөс эрэмбэлэх алгоритмын ажиллах хугацаа нь оролтын өгөгдлийн хэмжээнээс квадрат хамааралтай байна.
Ерөнхийдөө аливаа алгоритмын гүйцэтгэлийн хугацааг дараах байдлаар илэрхийлж болно.
Шинж чанарыг судлах, алгоритмыг харьцуулахдаа тогтмол хүчин зүйлийг хаяж болно, учир нь хангалттай том N-ийн хувьд функцийн өсөлтийн дараалал нь тодорхойлох хүчин зүйл болдог. Үүнийг жишээгээр тайлбарлахад хялбар байдаг. Альтернатив 2 алгоритм байгаа гэж бодъё, эхнийх нь өсөлтийн квадрат дараалалтай, хоёр дахь нь шугаман функцээр тодорхойлогддог. Мөн бид эхний алгоритмын хэрэгжилтийг оновчтой болгоход ойрхон, програмыг орчин үеийн компьютер дээр гүйцэтгэдэг гэж бид үзэж байна. Үүний зэрэгцээ, хоёр дахь алгоритмын хэрэгжилт нь гайхалтай биш бөгөөд хуучирсан компьютер дээр хийгддэг. Гадны нөхцөл байдлын ийм тэнцвэргүй байдлыг тогтмол хүчин зүйлийн ялгааг ашиглан загварчилж болно (зөвшөөрөх, a). Жижиг N-ийн хувьд, жишээлбэл, 5 өгөгдөлтэй бол эхний алгоритмын гүйцэтгэх хугацаа хоёр дахь үеийнхээс бага байх болно.
Гэсэн хэдий ч, оролтын өгөгдлийн тоо нэмэгдэхийн хэрээр тооцоолоход илүү төвөгтэй хоёр дахь алгоритм нь бүх таагүй хүчин зүйлийг үл харгалзан эхнийхээс давах болно.
Тогтмол хүчин зүйлсийн утгууд ямар ч байсан, нэг алгоритмын тооцооллын нарийн төвөгтэй байдал нь нөгөө алгоритмын тооцооллын нарийн төвөгтэй байдлаас илүү байх үед оролтын өгөгдлийн тодорхой эргэлтийн цэг үргэлж байдаг бөгөөд үүнээс эхлэн алгоритмын өсөлтийн дараалал эхэлдэг. давамгайлах хүчин зүйл болох гүйцэтгэх хугацаа.
Алгоритмуудын тооцооллын нарийн төвөгтэй байдлын асимптотик тооцооллын талаархи аналитик үндэслэлийг гаргахын тулд уран зохиолд хэд хэдэн математик тэмдэглэгээг ашигладаг - O-тооцоо, -тооцоо, -тооцоо.
Үнэлгээ нь өсөлтийн ижил дараалалтай, тогтмол хүчин зүйлээр ялгаатай хязгааргүй олон тооны функцтэй харьцуулах явдал юм. Хангалттай том N-ийн хувьд шинжилж буй алгоритмын хурдыг тодорхойлсон функцээс дээш ба доор хязгаарлах тогтмолууд байвал функц олонлогт хамаарна. Тиймээс дараахь харилцааг бий болгоно.
O оноо нь дүн шинжилгээ хийсэн алгоритмын функцийг зөвхөн дээрээс нь хязгаарладаг -score-ийн дэд хэсэг юм. Өөрөөр хэлбэл, O үнэлгээ нь шинжлэгдсэн алгоритмын хамгийн муу тохиолдлыг асимптотоор дүрсэлдэг. Энэхүү үнэлгээг дүн шинжилгээ хийхэд ихэвчлэн ашигладаг. Илүү бага ашиглагддаг нь дүн шинжилгээ хийсэн алгоритмын функцийг доороос нь хязгаарладаг тооцоолол юм (хамгийн сайн тохиолдол).
Алгоритмуудын тооцооллын нарийн төвөгтэй байдлын асимптотик тооцооллын дунд дараахь функцууд түгээмэл байдаг.
шугаман O(N) (цаг хугацаа нь өгөгдлийн өсөлттэй пропорциональ);
квадрат O(N 2);
олон гишүүнт нарийн төвөгтэй O(N M), тухайлбал, куб төвөгтэй O(N 3);
экспоненциал нарийн төвөгтэй O(2N);
хүчин зүйлийн нарийн төвөгтэй байдал O(N!);
логарифмын нарийн төвөгтэй байдал O(log(N)) (суурь 2 логарифм гэсэн үг);
шугаман-логарифм нарийн төвөгтэй O(N * log(N)) ;
Тогтмол тооцооллын нарийн төвөгтэй O(1) (цаг хугацаа нь өгөгдлийн хэмжээнээс хамаарахгүй).
Энэ жагсаалт нь бусад функцүүдийн харагдах байдлыг үгүйсгэхгүй боловч практикт тулгарсан тохиолдлын дийлэнх хувийг энд жагсаав. Эдгээр функцийг хамгийн үр дүнтэйгээс хамгийн бага хүртэл дараах байдлаар эрэмбэлж болно.
Боловсруулсан алгоритмуудын тооцооллын нарийн төвөгтэй байдлыг аль болох хязгаарлах хэрэгтэй. Эдгээр тооцооллын хоорондын хамаарлыг гүйцэтгэсэн зааврын тоог тодорхой жишээн дээр үзүүлснээр мэдрэгдэж болно, жишээ нь N = 5, 10, 25, 100, 500 (ойлголтыг хялбарчлахын тулд бид тогтмол коэффициентүүд ижил байна гэж үзнэ). Ийм хэмжээний өгөгдлийн тусламжтайгаар бид дараах үзүүлэлтүүдийг олж авдаг.
|
маш олон |
маш олон |
||||
|
маш олон |
маш олон |
маш олон |
Тогтмол тооцооллын нарийн төвөгтэй байдал нь хамгийн тохиромжтой тохиолдол бөгөөд ихэнхдээ ийм нарийн төвөгтэй алгоритмууд асуудлыг шийдвэрлэхэд байдаггүй. Логарифмын функц нь мөн харьцангуй удаан өсдөг. Шугаман болон шугаман-логарифм функцууд нь зөвшөөрөгдөх хурдаар өсдөг. Бусад функцууд мэдэгдэхүйц хурдацтай хөгжиж байна.
Хэрэв хөтөлбөр нь судалгааны хөтөлбөр бол зөвшөөрөгдөх хамгийн их төвөгтэй байдал нь олон гишүүнт, ялангуяа куб байна. Тооцооллын нарийн төвөгтэй алгоритмууд нь зөвхөн N-ийн жижиг утгуудад л хамаарна, эс тэгвээс асуудалд хүрч болох тооцооллын зардал бүхий компьютерийн шийдэл байхгүй болно.
Үүний зэрэгцээ, ерөнхийдөө үр дүнд хүрэх боломж төдийгүй хэрэглэгчийн хүлээн зөвшөөрөгдсөн хүлээх хугацаа чухал байдаг арилжааны програм хангамжийн салбарт нарийн төвөгтэй байдал нь шугаман-логарифмээс давсан алгоритмыг бараг ашигладаггүй.
Тооцооллын нарийн төвөгтэй байдлын гүехэн тооцоо
Алгоритм бүтээх, дүн шинжилгээ хийх сонгодог уран зохиолд тодорхой алгоритмын тооцооллын нарийн төвөгтэй байдлын талаархи таамаглалыг аналитик байдлаар гаргаж, нотлох нарийн математик тооцоололд ихээхэн анхаарал хандуулдаг. Дадлагажигч програмистууд энэ үйл явцад бага анхаарал хандуулж, математикчдын албан ёсны хатуу хэв маягаар үндэслэл гаргахаас зайлсхийдэг. Гэсэн хэдий ч, хэрэв тодорхой алгоритмыг хэрэгжүүлэх програмын код нь тийм ч эргэлзээгүй бол зөвхөн програмын кодын ерөнхий бүтцээс тооцооллын нарийн төвөгтэй байдлын талаар зөв таамаглал дэвшүүлэх боломжтой юм шиг санагддаг.
Нарийвчилсан дүн шинжилгээ хийхгүйгээр тооцооллын нарийн төвөгтэй байдлыг "нүдээр" өнгөцхөн үнэлэх зарим зөвлөмжийг доор харуулав.
Бүх энгийн зааварчилгаа - илэрхийллийг үнэлэх, хувьсагчийг хуваарилах, оролт-гаралт, утгыг буцаах - O(1) тогтмол тооцооллын нарийн төвөгтэй энгийн блокууд гэж ойлгогдох ёстой.
Зааваруудын дарааллын тооцооллын нарийн төвөгтэй байдал нь түүнд багтсан зааврын хамгийн их төвөгтэй байдалтай тэнцүү байна.
Хэрэв нөхцөлт шилжилтийн гал асаах магадлалын талаар тусгай мэдээлэл байхгүй бол бүх боломжит нөхцөлт шилжилтүүд, түүний дотор далд шилжилтийг (өөр орхигдуулсан, анхдагч салбарууд) адил магадлалтай гэж үзэх хэрэгтэй. Зааврын блок бүрийн нарийн төвөгтэй байдлыг тусад нь тооцож, дараа нь тэдгээрийн хамгийн дээд хэмжээг сонгох бөгөөд энэ нь бүхэлдээ нөхцөлт бүтцийн үнэлгээний үр дүн болно.
Хэрэв заавар нь давталтын тоо нь N-ээс хамаарах давталтын биед байгаа бол зааврын тооцооллын нарийн төвөгтэй байдлыг шугаман функцээр үржүүлнэ.
Хоорондоо үүрлэсэн N-аас хамааралтай хоёр гогцооны тооцооллын нарийн төвөгтэй байдлыг квадрат функцээр тайлбарлах магадлалтай. Үүний дагуу 3 түвшний үүрлэх нь кубын нарийн төвөгтэй байдалд нийцдэг.
Хэрэв алгоритм нь оролтын багц өгөгдлийг хэсэг болгон хувааж, дараа нь ижил алгоритмаар тусад нь рекурсив байдлаар боловсруулдаг бол тооцооллын нарийн төвөгтэй байдал нь логарифм юм.
Олон алгоритмууд рекурсив, i.e. өөр аргументуудтай өөрсдийгөө дууддаг. Үүний зэрэгцээ, рекурсээс гарахын тулд үргэлж "гарах нөхцөл" байх ёстой - рекурсийг эвдэж, зарим энгийн үйлдэл хийдэг аргументуудын утгууд. Хамгийн энгийн жишээ бол хүчин зүйлийн тооцооллын функц юм.
intхүчин зүйл ( int _x)
хэрэв(_x< 1)
буцах 0;
өөр бол(_x == 1)
буцах 1;
буцах _x * факториал(_x - 1);
Үндсэн нөхцлийн эхний хоёр салбар нь энгийн заавар бөгөөд тэдгээрийн тооцооллын нарийн төвөгтэй байдлыг O(1) гэж тооцдог. Сүүлчийн салбарын хувьд нарийн төвөгтэй байдлыг гэж нэрлэгддэг зүйлээр тайлбарладаг давтагдах хамаарал:
Тооцооллын нарийн төвөгтэй байдлын тооцоог гаргахын тулд дахилтын хамаарлыг аналитик аргаар илрүүлэх шаардлагатай. Хариултуудыг тодорхой нарийн төвөгтэй байдлын томъёонд хүчин зүйлийн алхам алхмаар орлуулснаар бид шугаман хамаарлыг олж авна.
Алгоритмын шинжилгээ -
Шинжилгээний төрлүүд
Хамгийн муу хэрэг: T(n)
Дундаж тохиолдол: T(n)
Асимптотик тооцоо
О
f (n) = O(g(n)) Þ
($c > 0, n 0 >
O(g(n)) = (f (n) : $ c > 0, n 0 >
Жишээ: 2n 2 = O(n 3)
Нэгтгэх төрөл
хэрэв (х< r) //1
 |
Рекурсын мод: T(n) = 2*T(n/2) +cn, –const-тэй, c>0
Рекурсив алгоритмыг үнэлэх арга зүй.
Давталтын арга
T (n) томъёонд үндэслэн бид T (n) томъёоны баруун талд байрлах жижиг элементийн томъёог бичнэ.
Үүссэн томъёоны баруун талыг анхны томъёонд орлуулна
Бид томъёог T(n) функцгүй цуврал болгон өргөжүүлэх хүртэл эхний хоёр алхамыг гүйцэтгэнэ.
Үр дүнгийн цувааг арифметик эсвэл геометрийн прогресс дээр үндэслэн тооцоолъё
T(n)=T(n-1)+n, T(1)=1
T(n)=θ(g(n)), g(n)=?
T(n-1)=T(n-2)+(n-1)
T(n-2)=T(n-3)+(n-2)
T(n-3)+(n-2)+(n-1)+n=…
1+…(n-2)+(n-1)+n=
Рекурсын мод - харилцааг өөртөө орлуулах график арга
T(n)=2T(n/2)+n 2
T(n/4) T(n/4) T(n/4) T(n/4)
(n/2) 2 (n/2) 2 log n (1/2)*n 2
(n/4) 2 (n/4) 2 (n/4) 2 (n/4) 2 (1/4)*n 2
Орлуулах арга
- Шийдлийг таах (санал болгох).
- Уусмалыг индукц ашиглан шалгана уу
- Тогтмолыг олж, орлуулах
T(n) = 2T(n/2) + n
T(n) = (n log n)
Индукцийн нөхцөл: T(n) ≤ с * n* log n, c>0
Энэ тооцоо үнэн байх болтугай n/2
T(n/2) ≤ c*(n/2)*лог(n/2)
Үүнийг анхны томъёонд орлуулъя T(n)
T(n) ≤ 2*(c*(n/2)*log(n/2))+n ≤
c*n*log(n/2)+n =
c*n*log n - c*n*log 2 +n =
c*n*log n - c*n +n ≤
c*n*log n
c≥1, n ≥ 2
Урсгал тооцооллын үндсэн теорем
T (n) = aT (n/b) + f (n), a ≥ 1, b > 1, f (n) − (f (n) > 0, n > n0)
Олон гишүүнт хугацаанд массивыг эрэмбэлэх алгоритмууд
Эрэмбэлэх гэдэг нь өгөгдсөн зүйлд зориулж объектуудыг дахин цэгцлэх үйл явц юм
тодорхой дарааллаар нэгтгэдэг (өсөх
эсвэл буурах).
Эрэмбэлэх зорилго нь ихэвчлэн дараагийнхыг хөнгөвчлөх явдал юм
эрэмбэлэгдсэн багц дахь элементүүдийг хайх.
Энгийн оруулах төрөл
оруулахаар эрэмбэлэхийг хүчингүй болгох(a , int N)
хувьд (i=1; i< N; i++)
(j=i-1; (j>=0)"&& (x< a[j]); j--)
a = a[j];
Энгийн оруулах төрөлд дүн шинжилгээ хийх
Харьцуулалтын тоо:
C (N) = 1 + 2 + 3 + ... + N - 1 = (N * (N -1))/2= O (N 2)
Нийт хугацаа: T(N) = θ(N 2)
Энгийн солилцоогоор эрэмбэлэх. Бөмбөлөг арга.
хүчингүй бөмбөлгийг эрэмбэлэх (түлхүүр a, int N)
хувьд (i=0; i хувьд (j=N-l; j>i; j--) хэрэв (a > a[j]) ( x = a[j]; a[j] = a[j-1]; a[ j -1] = x; Энгийн солилцоогоор эрэмбэлэх шинжилгээ Хамгийн муу тохиолдол: урвуу дараалсан массив Харьцуулалтын тоо: C(N) = (N - 1) + (N - 2) + ... + 1 = (N * (N-1))/2 = O(N 2) Нийт хугацаа: T(N) = θ(N 2) Нэмэлт Зангилаа* _Нэмэх(Зангилаа *r, T s) r = шинэ зангилаа(ууд); өөрөөр бол< r->inf) r->зүүн = _Нэмэх(r->зүүн, s); r->баруун = _Нэмэх(r->баруун, s); Модноос элементийг устгаж байна Үндэс n ба K түлхүүртэй T мод. модноос T зангилааг K түлхүүрээр (хэрэв байгаа бол) устгана. Алгоритм: Хэрэв T мод хоосон байвал зогсоо; Үгүй бол K-г үндсэн зангилааны n-ийн X түлхүүртэй харьцуул. Хэрэв K>X бол T-ийн баруун дэд модноос K-г рекурсив аргаар устгана; Хэрэв К Хэрэв K=X бол гурван тохиолдлыг авч үзэх шаардлагатай. Хэрэв хоёр хүүхэд байхгүй бол бид одоогийн зангилааг устгаж, эцэг эхийн зангилааны холбоосыг дахин тохируулна; Хэрэв хүүхдүүдийн аль нэг нь алга бол бид үндсэн зангилааны харгалзах утгуудын оронд m хүүхдийн талбаруудын утгыг тавьж, хуучин утгыг нь дарж бичиж, m зангилаа эзэлсэн санах ойг чөлөөлнө; Хэрэв хоёр хүүхэд хоёулаа байгаа бол өгөгдсөний хажууд байгаа m зангилаа олно; m-ээс n хүртэлх өгөгдлийг (хүүхдийн элементүүдийн холбоосоос бусад) хуулах; m зангилаа рекурсив устгах. Дараахь элементийг өгсөн Өгөгдсөн: мод T ба түлхүүр x X нь модны сүүлчийн элемент бол NULL эсвэл NULL-ийн хажууд байгаа элемент рүү заагчийг буцаана. Алгоритм: Хоёр хэргийг тусад нь авч үздэг. Хэрэв x оройн баруун дэд мод хоосон биш бол x-ийн хажууд байгаа элемент нь энэ дэд модны хамгийн бага элемент болно. Үгүй бол х оройн баруун дэд мод хоосон байвал. Эцэг эхийнх нь зүүн хүүхэд болох оройг олох хүртэл бид x-ээс дээш хөдөлнө. Энэ эцэг эх (хэрэв байгаа бол) хайж буй элемент байх болно. Зангилаа оруулж байна AVL мод руу шинэ түлхүүр оруулах нь энгийн хайлтын модтой ижил аргаар хийгддэг: бид мод уруудаж, одоогийн зангилаа дахь түлхүүрийг харьцуулсан үр дүнгээс хамааран баруун эсвэл зүүн хөдөлгөөний чиглэлийг сонгоно. оруулсан түлхүүр. Цорын ганц ялгаа нь рекурсаас буцаж ирэхэд (өөрөөр хэлбэл баруун эсвэл зүүн дэд модны аль нэг хэсэгт түлхүүрийг оруулсны дараа) одоогийн зангилаа дахин тэнцвэрждэг. Хөдөлгөөний зам дагуух аливаа зангилаанд ийм оруулга хийснээр үүсэх тэнцвэргүй байдал нь хоёроос хэтрэхгүй бөгөөд энэ нь дээр дурдсан тэнцвэржүүлэх функцийг зөв ашиглах явдал юм. Зангилаа арилгах AVL модноос оройг арилгахын тулд алгоритмыг үндэс болгон авдаг бөгөөд үүнийг стандарт хоёртын хайлтын модноос зангилаа арилгахад ихэвчлэн ашигладаг. Өгөгдсөн k товчлуураар р зангилаа олно, баруун дэд модноос min зангилааг хамгийн жижиг товчлуураар олоод устгасан p зангилааг олсон min зангилаагаар солино. Хэрэгжүүлэх явцад хэд хэдэн сонголт гарч ирдэг. Юуны өмнө, хэрэв олдсон p зангилаа нь баруун дэд модгүй бол AVL модны шинж чанарын дагуу зүүн талд энэ зангилаа нь зөвхөн нэг хүүхэд зангилаатай байж болно (мод 1 өндөр), эсвэл p зангилаа байна. навч хүртэл. Эдгээр хоёр тохиолдолд та зүгээр л p цэгийг устгаад үр дүнд нь p-ийн зүүн талын зангилаа руу заагчийг буцаана. Одоо p-г баруун дэд модтой болгоё. Бид энэ дэд модноос хамгийн бага түлхүүрийг олдог. Хоёртын хайлтын модны өмчийн дагуу энэ түлхүүр нь модны үндэснээс эхлэн зүүн мөчрийн төгсгөлд байрладаг. Бид рекурсив findmin функцийг ашигладаг. removemin функц - өгөгдсөн модноос хамгийн бага элементийг устгах. AVL модны өмчийн дагуу баруун талд байгаа хамгийн бага элемент нь нэг зангилаатай эсвэл хоосон байна. Аль ч тохиолдолд та зүгээр л заагчийг баруун зангилаа руу буцааж, буцах замдаа (рекурсиас буцаж ирэхэд) тэнцвэржүүлэх хэрэгтэй. Хэш хүснэгтүүд, гинжлэх арга Шууд хаяглалт нь жижиг багц товчлууруудад ашиглагддаг. Динамик олонлогийг тодорхойлох шаардлагатай бөгөөд элемент бүр нь U = (0,1,..., m - 1) олонлогоос түлхүүртэй, m нь тийм ч том биш, хоёр элемент ижил товчлуургүй болно. Динамик олонлогийг дүрслэхийн тулд байрлал эсвэл нүд бүр нь U түлхүүрийн зайн товчлууртай тохирч байгаа массив (шууд хаяглагдсан хүснэгт) T-г ашигладаг. k нүд нь k товчлууртай олонлогийн элементийг заана. Хэрэв олонлог нь k товчлууртай элемент агуулаагүй бол T[k] = NULL болно. Түлхүүр хайх ажиллагаа нь цаг хугацаа шаарддаг O(1) Шууд хаягийн сул талууд: Хэрэв түлхүүрийн зай U том бол |U| хэмжээтэй T хүснэгтийг хадгална Боломжтой санах ойн хэмжээ болон товчлуурын зайны хэмжээ зэргээс шалтгаалан боломжгүй юм аа гэхэд боломжгүй юм Үнэн хэрэгтээ хадгалагдсан түлхүүрүүдийн K багц нь U түлхүүрийн орон зайтай харьцуулахад бага байж болох бөгөөд энэ тохиолдолд T хүснэгтэд хуваарилагдсан санах ойг их хэмжээгээр зарцуулдаг. Хэш функц нь T хүснэгт дэх U олонлогийн элементүүдийн байршлыг тодорхойлдог h функц юм. Хэшгийн үед k түлхүүртэй элементийг h(k) нүдэнд хадгалдаг бөгөөд h хэш функц нь тухайн k түлхүүрийн нүдийг тооцоолоход хэрэглэгддэг. h функц нь U гол орон зайг хэш хүснэгтийн T [O..m - 1] нүднүүдэд буулгана: h: U → (0,1,..., m -1). h(k) утгыг k түлхүүрийн хэш утга гэнэ. Толь бичигт хадгалагдсан түлхүүрүүдийн K багц нь боломжит U түлхүүрүүдийн зайнаас хамаагүй бага байвал хэш хүснэгт нь шууд хаяглах хүснэгтээс хамаагүй бага зай шаарддаг. Хэш функцийн зорилго нь |U|-ийн оронд массивын индексүүдийн ажиллах хүрээг багасгах явдал юм утгууд, та зөвхөн m утгуудыг ашиглан авч болно. Санах ойн шаардлагыг θ(|K|) болгон бууруулж болох ба хэш хүснэгт дэх элементийг хайх хугацаа нь O(1)-тэй тэнцүү хэвээр байна - энэ нь хайлтын дундаж хугацааны хязгаар юм, харин шууд- хаяглалтын хүснэгт энэ хязгаар нь хамгийн муу тохиолдолд хүчинтэй. Мөргөлдөөн гэдэг нь хоёр түлхүүр нэг нүдэн дээр байрлах нөхцөл юм. Жишээ нь h(43) = h(89) = h(112) = k Гинжингийн арга: Санаа: Олонлогийн элементүүдийг жагсаалттай ижил хэш утгаар хадгалах. Шинжилгээ Хамгийн муу тохиолдол: хэрэв олонлогийн бүх элементийн хэш функц ижил утгыг үүсгэдэг бол. Хандалтын хугацаа нь |U-тэй Θ(n). |
= n. Дундаж тохиолдол: хэш утгууд жигд тархсан тохиолдолд. Түлхүүр бүр нь бусад товчлуурууд хаана унаснаас үл хамааран хүснэгтийн аль ч нүдэнд байх магадлалтай. T хүснэгт өгөгдсөн ба түүнд n түлхүүр хадгалагдсан байг. Дараа нь a = n/m нь хүснэгтийн нүднүүдийн түлхүүрүүдийн дундаж тоо юм. Алга болсон элементийг хайх хугацаа нь Θ(1 + α) байна. Хэш функцийн утгыг тооцоолох тогтмол хугацаа нэмээд жагсаалтыг эцэс хүртэл туулах хугацаа, учир нь Жагсаалтын дундаж урт нь α бол үр дүн нь Θ(1) + Θ(α) = Θ(1 + α) болно. Хүснэгтийн нүднүүдийн тоо нь түүнд хадгалагдсан элементүүдийн тоотой пропорциональ байвал n = O(m) ба α = n/m = O(m)/m = O(1) гэсэн үг. Хэш хүснэгтийн элементэд дунджаар Θ(1) хугацаа шаардагдана. Үйл ажиллагаа Хүснэгтэд элемент оруулах Устгах Мөн O(1) хугацаа шаардагдана Хэш функцийг сонгох Түлхүүрүүд нь бүх нүдэнд жигд тархсан байх ёстой Хэш функцийн товчлууруудын тархалтын загвар нь өгөгдлийн загвартай уялдаж болохгүй. (Жишээ нь, өгөгдөл нь тэгш тоо). Арга: Хуваах арга Үржүүлэх арга Хуваах арга h (k) = k mod m Жижиг хуваагчийн асуудал m Жишээ №1. м = 2бүх товчлуурууд тэгш байна Þ сондгой нүд нь тэгш биш байна дүүрэн. Жишээ №2. m = 2 rÞ хэш нь дээрх битүүдээс хамаардаггүй r. Үржүүлэх арга Болъё м= 2 r , түлхүүрүүд нь w-бит үгс юм. h(k) = (A k mod 2 w) >> (w - r),Хаана A mod 2 = 1 ∩ 2 w-1< A< 2 w Та сонгох ёсгүй АОйролцоо 2w-1Тэгээд 2w Энэ арга нь хуваах аргаас илүү хурдан байдаг Үржүүлэх арга: жишээ m = 8 = 2 3 , w = 7 Нээлттэй хаяг: хайх Хайлт нь мөн дараалсан судалгаа юм Утга нь олдвол амжилт Хоосон нүд олох эсвэл хүснэгтийг бүхэлд нь үзэхэд бүтэлгүйтэх. Судалгааны стратеги Шугаман - h(k, i) = (h′(k) + i) mod m Энэ стратегийг хэрэгжүүлэхэд хялбар боловч асуудалтай тулгардаг урт дараалал үүсгэхтэй холбоотой анхдагч кластер эзлэгдсэн эсийн идэвхжил, энэ нь хайлтын дундаж хугацааг нэмэгдүүлдэг. Квадрат h(k, i) = (h′(k) + c 1 i+ c 2 i 2) mod m Энд h′(k) нь ердийн хэш функц юм Давхар хэш - h(k,i) = (h 1 (k) + i h 2 (k)) mod m. Давхар хэш Энэ арга нь маш сайн үр дүнг өгдөг боловч h 2 (k) нь m-тэй харьцуулах ёстой. Үүнд хүрч болно: m-ийг хоёрын зэрэглэл болгон ашиглаж, h 2 (k) болговол зөвхөн сондгой тоо гарна m = 2 r иh 2 (k)- хачин. м- анхны тоо, утгууд h 2 – m-ээс бага эерэг бүхэл тоо Энгийн хувьд м суулгаж болно h1(k)=k mod m h2(k)=1+(k mod m’) m'-ээс бага (m' =м-1 эсвэл м-2) Нээлттэй хаяглалт: Оруулах жишээ А хүснэгтийг өгье: Давхар хэш h2(k)=1+(k mod 11) Элементийг хаана оруулах вэ? Нээлттэй хаяглалтын шинжилгээ Нэг төрлийн хэш хийх нэмэлт таамаглал: Түлхүүр бүр m-ийн аль нэгийг хүлээн авах магадлалтай. хүснэгт хайгуулын дарааллын сэлгэлт бусад түлхүүрүүдээс үл хамааран. Алга болсон элементийг хайж олох Амжилттай хайлт хийх туршилтын тоо Нээлттэй хаяглалт А< 1 - const Þ O(1)
Тэр яаж биеэ авч явдаг вэ? Х: Хүснэгт 50% Þ2 судалгааны гүйцэтгэл Хүснэгт Þ 10 судалгаа 90% бүрэн хийгдсэн байна Хүснэгт нь 100% бүрэн Þ m судалгаа юм Шуналтай сонголтын зарчим Энэ нь оновчлолын асуудалд хамаатай гэж тэд хэлж байна шуналтай сонголтын зарчим, хэрэв орон нутгийн оновчтой сонголтуудын дараалал нь дэлхийн хэмжээнд оновчтой шийдлийг өгдөг бол. Ихэвчлэн оновчтой байдлын нотолгоо нь дараах загварыг дагаж мөрддөг. Эхний алхамд шунахайн сонголт нь оновчтой шийдэлд хүрэх замыг хаадаггүй нь батлагдсан: шийдэл болгонд шунахайн сонголттой нийцэх өөр нэг хувилбар байдаг бөгөөд эхнийхээс муу зүйл байхгүй. Эхний алхамд шунахайн сонголт хийсний дараа үүсэх дэд асуудал нь анхныхтай төстэй болохыг харуулж байна. Аргумент нь индукцээр төгсдөг. Дэд ажилд хамгийн тохиромжтой Асуудал нь өмчтэй байна гэдэг дэд асуудлын оновчтой байдал, хэрэв асуудлын оновчтой шийдэл нь түүний бүх дэд асуудлын оновчтой шийдлүүдийг агуулж байвал. Хаффманы кодын бүтээн байгуулалт Аливаа мессеж нь цагаан толгойн үсгийн дараалсан тэмдэгтүүдээс бүрддэг. Ихэнхдээ санах ойг хэмнэх, мэдээлэл дамжуулах хурдыг нэмэгдүүлэхийн тулд мэдээллийг шахах ажил үүсдэг. Энэ тохиолдолд тэмдэгтийг кодлох тусгай аргыг ашигладаг. Эдгээрт мэдээллийн төрлөөс хамааран 20% -иас 90% хүртэл шахалтыг хангадаг Huffman кодууд багтдаг. Хаффманы алгоритм нь шахсан текстэнд ашигласан тэмдэгтүүдийн давтамж дээр үндэслэн оновчтой тэмдэгтийн кодыг олдог. Хаффманы алгоритм бол шунахайн алгоритмын жишээ юм. 100,000 тэмдэгтийн урттай файлд тэмдэгтийн давтамжийг мэддэг гэж үзье. Бид тэмдэгт бүрийг код үг гэж нэрлэдэг битүүдийн хязгаарлагдмал дараалал хэлбэрээр дүрсэлсэн хоёртын кодыг бүтээх хэрэгтэй. Бүх кодын үг ижил урттай нэг төрлийн кодыг ашиглах үед нэг тэмдэгтэд дор хаяж гурван бит зарцуулагдах бөгөөд файлыг бүхэлд нь 300,000 бит шаарддаг. Байнга тохиолддог тэмдэгтүүдийг битийн богино дарааллаар, ховор тохиолддог тэмдэгтүүдийг урт дараалалтай кодчилвол тэгш бус код нь илүү хэмнэлттэй байх болно. Кодлох үед файл бүхэлдээ зардал гарах болно (45*1 + 13*3 + 12*3 + 16*3 + 9*4 + 5*4)*1000 = 224000. Өөрөөр хэлбэл, тэгш бус код нь ойролцоогоор 25% хэмнэлт өгдөг. Угтвар кодууд Өөр өөр тэмдэгтүүдийг төлөөлөх хоёр битийн дараалал тус бүрийн аль нь ч нөгөөгийн угтвар биш кодуудыг авч үзье. Ийм кодыг угтвар код гэж нэрлэдэг. Кодлох үед тэмдэгт бүр өөрийн кодоор солигддог. Жишээлбэл, abc мөр нь 0101100 шиг харагдаж байна. Угтвар кодын хувьд тайлах нь өвөрмөц бөгөөд зүүнээс баруун тийш явагдана. Угтвар кодоор кодлогдсон текстийн эхний тэмдэгт нь өвөрмөц байдлаар тодорхойлогддог, учир нь түүний код нь өөр тэмдэгтийн эхлэл байж болохгүй. Энэ тэмдгийг тодорхойлж, кодын үгээ хаясны дараа бид үлдсэн битүүдийн үйл явцыг давтан хийнэ. Тайлбарыг үр дүнтэй хэрэгжүүлэхийн тулд кодын талаарх мэдээллийг тохиромжтой хэлбэрээр хадгалах хэрэгтэй. Нэг боломж бол кодыг дүрслэх явдал юм код хоёртын мод, навч нь кодлох тэмдэгтүүдтэй тохирч байна. Энэ тохиолдолд язгуураас кодлогдсон тэмдэг хүртэлх зам нь битүүдийн кодчиллын дарааллыг тодорхойлдог: модны дагуу зүүн тийш шилжихэд 0, баруун тийш шилжихэд 1 болно. Дотоод зангилаа нь харгалзах дэд модны навчны давтамжийн нийлбэрийг заана. Өгөгдсөн файлын оновчтой код нь навч биш орой бүр хоёр хүүхэдтэй байдаг хоёртын модтой үргэлж тохирдог. Харгалзах мод нь нэг хүүтэй оройтой тул жигд код нь оновчтой биш юм. Зарим С багцын бүх тэмдэгтүүдийг ашигладаг файлын оновчтой угтвар кодын мод бөгөөд зөвхөн тэдгээрт яг | C | тэмдэг тус бүрт нэгийг үлдээдэг бөгөөд яг | C | - Навч биш 1 зангилаа. Угтвар кодтой харгалзах T модыг мэдсэнээр файлыг кодлоход шаардагдах битийн тоог олоход хялбар байдаг. С цагаан толгойн c тэмдэгт бүрийн хувьд f[c] нь файлд тохиолдсон тохиолдлын тоог, dT(c) түүний харгалзах хуудасны гүн, иймээс c кодчилсон битүүдийн дарааллын уртыг тэмдэглэе. Дараа нь файлыг кодлохын тулд танд хэрэгтэй болно: Энэ утгыг модны өртөг гэж нэрлэдэг T. Энэ утгыг багасгах шаардлагатай. Хаффманоновчтой угтвар кодыг бүтээх шуналтай алгоритмыг санал болгосон. Алгоритм нь | олонлогоос эхлэн доороос дээш хүртэл оновчтой кодтой тохирох T модыг бүтээдэг. C | навч, хийх | C | - 1 нэгдэл. Тэмдэг тус бүрийн хувьд түүний давтамжийг f [c] зааж өгсөн болно. Нэгтгэх хоёр объектыг олохын тулд нэн тэргүүнд f давтамжийг ашиглан нэн тэргүүний Q дарааллыг ашигладаг - хамгийн бага давтамжтай хоёр объектыг нэгтгэдэг. Нэгтгэсний үр дүнд шинэ объект (дотоод орой) олж авах бөгөөд давтамжийг нэгтгэсэн хоёр объектын давтамжийн нийлбэртэй тэнцүү гэж үздэг. Энэ орой нь дараалалд нэмэгддэг. Хаффман ( C)
1. n ←│C│ │ C
│- хүч C 2. Q ← C
Q - тэргүүлэх дараалал 3. төлөөби ← 1 руу n-1 4. хийх z ← Зангилаа үүсгэх() z – f, зүүн, баруун талбаруудаас бүрдэх зангилаа 5. x ← зүүн [z] ← Бүртгэлээс хасах(А) 6. y ← баруун [z] ← Бүртгэлээс хасах(А) 7. f[z] ← f[x] + f[y] 8. Дараалалд оруулах(Q, z) 9. буцах Бүртгэлээс хасах(Q) модны үндсийг буцаана Зэрэг Дараалал нь хоёртын овоолгын хэлбэрээр хэрэгждэг. Та O(n)-д дараалал үүсгэж болно. Алгоритм нь n-1 удаа гүйцэтгэсэн гогцооноос бүрдэнэ. Дарааллын үйлдэл бүр O(log n)-д дуусдаг. Нийт ажиллах хугацаа нь O(n log n) байна. Сүлжээний барилгын асуудал Үүссэн газар: харилцаа холбоо, замын сүлжээ. Өгөгдсөн:олон сүлжээний зангилаа (хостууд, хотууд). Шаардлагатай:хамгийн бага нийт ирмэгийн жинтэй сүлжээг барих (сүлжээний кабелийн урт, замын урт). График загвар:сүлжээний зангилаанууд нь графикийн зангилаа, E = V 2, бид бүх ирмэгийн жинг мэддэг. Үр дүн:үнэгүй мод. MOD хайх хандлага Бид А модыг нэг нэгээр нь нэг ирмэгийг нэмж бүтээдэг ба давталт бүрийн өмнө одоогийн мод нь зарим MOD-ийн дэд олонлог юм. Алгоритмын алхам бүрт бид энэ шинж чанарыг зөрчихгүйгээр А-д нэмж болох ирмэгийг (u, v) тодорхойлно. Ийм ирмэгийг бид аюулгүй гэж нэрлэдэг Ерөнхий MST(G, w) 2 байхад А нь MOD биш 3 do A-д аюулгүй ирмэгийг (u, v) ол 4 A ← A U ((u, v)) ____________________________________________________________________________ Хавирганы ангилал 1. Модны хавирга(модны ирмэгүүд) нь G графикийн ирмэгүүд. Энэ ирмэгийг шалгах үед v орой нээлттэй байвал ирмэг (u, v) нь модны ирмэг юм. 2. Арын ирмэгүүд(арын ирмэгүүд) нь гүн дэх эхний хайлтын модны u оройг өвөг vтэй холбох ирмэгүүд (u,v) юм. Чиглүүлсэн графикт тохиолдож болох мөчлөгийн ирмэгийг арын ирмэг гэж үзнэ. 3. Шулуун хавирга(урагш ирмэгүүд) нь модны ирмэг биш ирмэгүүд (u,v) бөгөөд гүн дэх эхний хайлтын модны u оройг өөрийн удам v-тэй холбодог. 4. Хөндлөн хавирга(хөндлөн ирмэгүүд) - графикийн бусад бүх ирмэгүүд. Тэд өөр нэг оройн өвөг дээдэс байхгүй үед ижил гүнээс эхлээд хайлтын модны оройг холбож, эсвэл өөр өөр модны оройг холбож болно. DFS алгоритмыг өөрчлөх боломжтой бөгөөд ингэснээр үйл ажиллагааны явцад тулгарсан ирмэгүүдийг ангилах болно. Гол санаа нь ирмэг бүрийг (u, v) эхлээд шалгахдаа v оройн өнгийг ашиглан ангилж болно (гэхдээ шулуун ба хөндлөн ирмэгийг ялгадаггүй). Эхний тохиолдол нь алгоритмын тодорхойлолтоос шууд гардаг. Хоёрдахь тохиолдлыг авч үзвэл, саарал орой нь үргэлж DFS_Visit процедурын идэвхтэй дуудлагын стектэй харгалзах удамшлын шугаман гинжийг үүсгэдэг гэдгийг анхаарна уу; саарал оройн тоо нь гүн-эхний хайлтын модны сүүлчийн нээлттэй оройн гүнээс нэгээр их байна. Хайгуул нь үргэлж хамгийн гүн саарал оройноос эхэлдэг тул өөр саарал оройд хүрсэн ирмэг нь анхны оройн өвөг дээдэст хүрдэг. Гурав дахь тохиолдолд бид эхний эсвэл хоёр дахь тохиолдолд хамаарахгүй үлдсэн ирмэгүүдтэй харьцаж байна. Хэрэв d [u] бол ирмэг (u, v) шулуун болохыг харуулж болно.< d [v], и перекрестным, если d [u] >d[v] ___________________________________________________________________________ Топологийн ангилах IN тэргүүлэх баганаирмэг бүр (u, v) нь v-ийн өмнө байна гэсэн үг Топологийн ангилахГрафик нь a дарааллын бүтээн байгуулалт бөгөөд a i ба a j-ийн хувьд дараахь зүйлийг агуулна: $(a i ,a j) Þ i< j. G = (V, E) чиг баримжаатай ациклик графын топологийн эрэмбэлэх нь түүний бүх оройгуудын шугаман эрэмбэлэх бөгөөд хэрэв G графикт ирмэг (u,v) байвал энэ дарааллын u v-ийн өмнө байрлана (хэрэв график бол байвал). цикл бус, ийм ангилах боломжгүй). Графикийг топологийн эрэмбэлэх нь түүний оройг хэвтээ шугамын дагуу бүх ирмэгийг зүүнээс баруун тийш чиглүүлэхээр эрэмбэлэх гэж үзэж болно. Эрэмбэлэгдсэн дараалал: C2, C6, C7, C1, C3, C4, C5, C8 тус бүрийн хувьд(u in V) өнгө[u] = цагаан; // эхлүүлэх L = шинэ холбосон_жагсаалт; // L нь холбосон хоосон жагсаалт юм тус бүрийн хувьд (V дахь u) хэрэв (өнгө[u] == цагаан) TopVisit(u); буцах L; // L эцсийн тушаалыг өгдөг TopVisit(u) ( // u дээр хайлт эхлүүлнэ үү өнгө[u] = саарал; // зочилсон гэж тэмдэглэ тус бүрийн хувьд (V in Adj(u)) хэрэв (өнгө[v] == цагаан) TopVisit(v); L-ийн урд талд u-г хавсаргана; // дуусгасны дараа та жагсаалтад нэмнэ үү T (n) = Θ(V + E) Процедурууд Үүсгэх - Тохируулах (u)- нэг оройноос олонлог үүсгэх у. Хайх - Тохируулах (u)- орой нь хамаарах олонлогийг ол уямар багцад буцаж ирдэгзаасан элемент байрладаг. Үнэн хэрэгтээ, энэ нь олонлогийн элементүүдийн аль нэгийг буцаана (гэгддэг төлөөлөгчэсвэл удирдагч). Энэ төлөөлөгчийг багц бүрт өгөгдлийн бүтцээр өөрөө сонгодог (мөн цаг хугацааны явцад, тухайлбал, дуудлагын дараа өөрчлөгдөж болно Холбоо). Хэрэв зарим хоёр элементийн Find - Set дуудлага нь ижил утгыг буцаасан бол эдгээр элементүүд ижил олонлогт, эс бөгөөс өөр олонлогт байна гэсэн үг юм. Холбоо (у, v)- орой агуулсан олонлогуудыг нэгтгэнэ уТэгээд v Бид элементүүдийн багцыг хэлбэрээр хадгалах болно мод: нэг мод нэг багцад тохирно. Модны үндэс нь багцын төлөөлөгч (удирдагч) юм. Хэрэгжүүлснээр бид массив үүсгэнэ гэсэн үг эцэг эх, элемент бүрийн хувьд бид модны өвөг дээдсийн холбоосыг хадгалдаг. Модны үндэсийн хувьд бид тэдний өвөг дээдэс нь өөрсдийгөө (өөрөөр хэлбэл, энэ газарт холбоос гогцоо) гэж үзэх болно. Шинэ элемент үүсгэхийн тулд (үйл ажиллагаа Үүсгэх - Тохируулах), бид зүгээр л v орой дээр үндэслэсэн модыг үүсгэж, түүний өвөг эцэг нь өөрөө гэдгийг тэмдэглэдэг. Хоёр багцыг нэгтгэх (үйл ажиллагаа Холбоо(а,б)), бид эхлээд a байрлаж байгаа олонлогийн тэргүүлэгч, b байгаа олонлогийг олох болно. Хэрэв удирдагчид давхцаж байвал бид юу ч хийхгүй - энэ нь багцууд аль хэдийн нэгдсэн байсан гэсэн үг юм. Үгүй бол та b оройн өвөг нь f-тэй тэнцүү (эсвэл эсрэгээр) гэдгийг зүгээр л зааж өгч болно - ингэснээр нэг модыг нөгөө модтой холбоно. Эцэст нь удирдагчийг хайх ажиллагааны хэрэгжилт ( Хайх - Set(v)) нь энгийн: бид v оройноос өвөг дээдсээ авирч, үндэст хүрэх хүртлээ, i.e. харин өвөг дээдсийн тухай лавлагаа нь өөртөө хүргэдэггүй. Энэ үйлдлийг рекурсив байдлаар хэрэгжүүлэх нь илүү тохиромжтой. Замын шахалтын эвристик Энэхүү эвристик нь үйлдлийг хурдасгах зорилготой юм Хайх - Set() . Энэ нь дуудлагын дараа байх үед оршино Хайх - Set(v)бид хайж буй удирдагчаа олох болно хтохируул, дараа нь орой дээр байгаа гэдгийг санаарай vзам дагуу бүх оргилууд өнгөрөв - энэ бол энэ удирдагч юм х. Үүнийг хийх хамгийн хялбар арга бол тэдгээрийг дахин чиглүүлэх явдал юм эцэг эхэнэ оргилд х . Тиймээс өвөг дээдсийн массив эцэг эхутга нь бага зэрэг өөрчлөгдсөн: одоо байна шахсан өвөг массив, өөрөөр хэлбэл орой бүрийн хувьд ойрын өвөг дээдэс биш, харин өвөг дээдсийн өвөг дээдэс, өвөг дээдсийн өвөг дээдэс гэх мэтийг хадгалах боломжтой. Нөгөөтэйгүүр эдгээр зааврыг хийх боломжгүй гэдэг нь ойлгомжтой эцэг эхүргэлж удирдагч руу заадаг: өөрөөр хэлбэл, үйл ажиллагаа явуулах үед Холбооудирдагчдыг шинэчлэх хэрэгтэй болно O(n)элементүүд. Тиймээс массив руу эцэг эхяг л өвөг дээдсийн массив, магадгүй хэсэгчлэн шахагдсан байдлаар хандах ёстой. Замын шахалтын эвристикийг ашиглах нь логарифм асимптотик хүрэх боломжийг олгодог: нэг хүсэлтээр дунджаар Шинжилгээ Эхлэл - O(V) Давталт нь V удаа, extractMin үйлдэл бүр - O(logV) удаа, нийт O(V logV) удаа ажиллана. For давталт нь O(E) удаа ажиллана, бууруулах товчлуур нь O(logV) цаг авна. Нийт ажиллах хугацаа - O(V log V +E logV)= O(E logV) Хамгийн богино замын өмч Болъё p = (v 1 , v 2 ..... v k)- v 1 оройноос орой хүртэлх хамгийн богино зам vkөгөгдсөн жигнэсэн чиглүүлсэн графикт G = (U. E)жингийн функцтэй w: E → Rа p ij = (v i , v i+1 .....v j)- оройноос гарах p замын хэсэгчилсэн зам v iорой руу v ждур зоргоороо i ба j (1 ≤ i< j ≤ k).
Дараа нь p ij– оройноос хамгийн богино зам v iруу v i Дийкстра(G, w, s) ( тус бүрийн хувьд (V дахь u) ( // эхлүүлэх d [u] = +хязгааргүй өнгө [u] = цагаан d[s] =0 // эх үүсвэрийн дист нь 0 байна Q = new PriQueue(V) // бүх оройг Q-д тавина while (Q.nonEmpty()) ( // бүх оройг боловсруулах хүртэл u = Q.extractMin() // s-д хамгийн ойр байгаа u-г сонгоно уу тус бүрийн хувьд (V in Adj[u]) ( хэрэв (d[u] + w(u,v)< d[v]) { // Relax(u,v) d [v] = d [u] + w(u,v) Q. бууруулах товч(v, d[v]) өнгө [u] = хар Хэцүү байдлын үнэлгээ Беллман-Фордын алгоритм тодорхой хугацааны дотор дуусдаг O(V*E), 1-р мөрөнд эхлүүлэхэд |V|-ийн хувьд O(V) хугацаа шаардагдах тул - 2-4-р мөрөнд ирмэгийн дагуу 1 дамжуулалт хийхэд O(E) хугацаа, 5-7-р мөрөнд for давталтыг гүйцэтгэхэд O(E) хугацаа шаардагдана. . Алгоритмын асимптотик үнэлгээ Алгоритмын шинжилгээ -компьютерийн программуудын гүйцэтгэл, тэдгээрийн зарцуулдаг нөөцийн онолын судалгаа. Гүйцэтгэл - оролтын өгөгдлийн хэмжээнээс хамааран алгоритмын ажиллах хугацаа. T(n) функцээр тодорхойлогддог бөгөөд энд n нь оролтын өгөгдлийн эзэлхүүн юм Шинжилгээний төрлүүд Хамгийн муу хэрэг: T(n)– n хэмжээтэй аливаа оролтын өгөгдлийн хамгийн их хугацаа. Дундаж тохиолдол: T(n)– n хэмжээтэй аливаа оролтын өгөгдлийн хүлээгдэж буй хугацаа. Хамгийн сайн тохиолдол бол үйл ажиллагааны хамгийн бага хугацаа юм. Асимптотик тооцоо О- тэмдэглэгээ: асимптотик дээд хязгаар f (n) = O(g(n)) Þ ($c > 0, n 0 > 0 Þ 0 ≤ f (n) ≤ c g(n), n ≥ n 0) O(g(n)) = (f (n) : $ c > 0, n 0 > 0 Þ 0 ≤ f (n) ≤ c g(n), n ≥ n 0 ) Жишээ: 2n 2 = O(n 3)
Рекурсив алгоритмууд, асимптотик тооцоолол хийх. Жишээ Нэгтгэх төрөл sort(А,p,r) //p - массивын эхлэл, r – массивын төгсгөл T(n) хэрэв (х< r) //1 q=(p + r)/2; //1-р массивын дундыг тооцоол ангилах(A,p,q); //зүүн талыг эрэмбэлэх T(n/2) ангилах(A,q+1,r); //T(n/2)-ийн баруун талыг эрэмбэлэх нэгтгэх(p,q,r); //хоёр массивыг нэг n-д нэгтгэнэ Алгоритмуудын гүйцэтгэлийг үнэлэхийн тулд янз бүрийн аргыг ашиглаж болно. Хамгийн энгийн нь алгоритм бүрийг хэд хэдэн даалгавар дээр ажиллуулж, гүйцэтгэх хугацааг харьцуулах явдал юм. Өөр нэг арга бол үйлдлүүдийг тоолох замаар гүйцэтгэлийн хугацааг математикийн аргаар тооцоолох явдал юм. Зэрэглэлийн олон гишүүнтийн утгыг тооцоолох алгоритмыг авч үзье nөгөгдсөн цэг дээр x. Алгоритм 1- 0-ээс бусад нэр томъёо бүрийн хувьд xдараалсан үржүүлэх замаар өгөгдсөн хүчин чадал руу, дараа нь коэффициентээр үржүүлнэ. Дараа нь нөхцөлийг нэмнэ үү. Тооцоолол бир улирал ( i=1..n) шаарддаг биүржүүлэх Тэгэхээр, нийт 1 + 2 + 3 + ... + n = n(n+1)/2үржүүлэх Үүнээс гадна энэ нь зайлшгүй шаардлагатай n+1нэмэлт. Нийт n(n+1)/2 + n + 1= n 2 /2 + 3n/2 + 1үйл ажиллагаа. Алгоритм 2- Бид үүнийг гаргана x-s-ийг хаалтнаас гаргаж олон гишүүнтийг хэлбэрээр дахин бичнэ Жишээлбэл, Бид илэрхийлэлийг дотроос нь үнэлэх болно. Хамгийн дотоод хаалтанд 1 үржүүлэх, 1 нэмэх шаардлагатай. Үүний утгыг дараагийн хаалтанд ашиглана... Ингээд хаалт бүрт 1 үржүүлэг, 1 нэмэх нь... n-1зүйл. Мөн хамгийн гадна талын хаалтыг тооцоолсны дараа х-ээр үржүүлж, нэмнэ a 0. Нийт nүржүүлэх + nнэмэлтүүд = 2нүйл ажиллагаа. Ихэнхдээ ийм нарийвчилсан үнэлгээ хийх шаардлагагүй байдаг. Үүний оронд тэд зөвхөн n-ийг ихэсгэх үед үйлдлүүдийн тоо өсөх асимптот хурдыг өгдөг. f(n) = функц n 2 /2 + 3n/2 + 1байдлаар ойролцоогоор нэмэгддэг n 2 /2(харьцангуй аажмаар өсөн нэмэгдэж буй нэр томъёог бид хаядаг 3n/2+1). Тогтмол үржүүлэгч 1/2
Бид мөн тусгай тэмдгээр тэмдэглэсэн 1-р алгоритмын асимптотик тооцоог хасч, авдаг. O(n 2)["O big from an square" гэж уншина]. Энэ бол хамгийн дээд тооцоо юм, өөрөөр хэлбэл үйл ажиллагааны тоо (тиймээс ажиллах хугацаа) нь элементийн тооны квадратаас хурдан өсдөггүй. Энэ нь ямар байдгийг мэдэхийн тулд хэд хэдэн өөр функцүүдийн өсөлтийн хурдыг харуулсан тоонуудыг харуулсан хүснэгтийг харна уу. n*log n Хэрэв бид хүснэгтэд байгаа тоонууд нь микросекундтай тохирч байна гэж үзвэл асуудал гарна n=1048576ажиллах хугацаа бүхий алгоритмын элементүүд O(лог n)Энэ нь 20 микросекунд шаардагдах бөгөөд алгоритм нь эцэст нь болно O(n)- 17 минут, ажлын цагтай алгоритм O(n 2)- 12 хоногоос дээш... Одоо үнэлгээтэй 2-р алгоритмын давуу тал O(n)Алгоритм 1-ээс өмнө маш тодорхой байна. Хамгийн сайн тооцоо O(1)... Энэ тохиолдолд цаг хугацаа огт хамаардаггүй n, өөрөөр хэлбэл ямар ч тооны элементийн хувьд тогтмол. Тиймээс, O()- алгоритмын ажиллах хугацааны "тасарсан" тооцоолол бөгөөд энэ нь үйлдлүүдийн тоог яг нарийн томъёолохоос хамаагүй хялбар байдаг. Функцийг үнэлэхдээ хамгийн хурдан нэмэгддэг үйлдлүүдийн тоог функцээр авна. O()-г үнэлэхдээ тогтмолуудыг тооцохгүй. Ялангуяа, хэрэв алгоритм хоёулаа, жишээ нь. O(n*log n), энэ нь тэд адилхан үр дүнтэй гэсэн үг биш юм. Эхнийх нь 1000 дахин илүү үр дүнтэй байж болно. O() нь ердөө л тэдний цаг нь функцээр ойролцоогоор нэмэгддэг гэсэн үг юм n*log n. Тогтмолыг орхигдуулсан өөр нэг үр дагавар нь цаг хугацааны алгоритм юм O(n 2)алгоритмаас хамаагүй хурдан ажиллах боломжтой O(n) жижиг хувьд n... Эхний алгоритмын үйлдлүүдийн бодит тоо байж болох тул n2 + 10n + 6, хоёр дахь нь - 1000000н + 5. Гэсэн хэдий ч хоёр дахь алгоритм нь эрт орой хэзээ нэгэн цагт эхнийхийг гүйцэх болно ... n 2хамаагүй хурдан өсдөг 1000000н. Тэмдэгт доторх логарифмын суурь O()бичээгүй. Бид ямар ч бааз руу ижил аргаар шилжиж болно, энэ нь үүнийг бичих ямар ч утгагүй гэсэн үг юм. Тодорхойлолт Ялангуяа бид үүнийг хэлж чадна f(n) = 50nхарьяалагддаг O(n 2). Энд бид буруу тооцоолол хийж байна. Мэдээжийн хэрэг f(n)<= 50n 2
цагт n>1, гэхдээ илүү хүчтэй мэдэгдэл байх болно f(n) = O(n), оноос хойш C=50Тэгээд N=1зөв f(n)<= Cn, n>Н. Үнэлгээний хамт O(n)үнэлгээг ашигладаг Ω(n)["Omega big from en" гэж уншина]. Энэ нь функцийн өсөлтийн доод хязгаарыг илэрхийлдэг. Жишээлбэл, алгоритмын үйлдлүүдийн тоог функцээр тодорхойл f(n) = Ω(n 2). Энэ нь хамгийн амжилттай тохиолдолд ч гэсэн хамгийн багадаа хэмжээний захиалга гарна гэсэн үг юм n 2үйлдлүүд. Тооцооллыг мөн ашигладаг Θ(n)["Theta from en"] нь эрлийз юм O()Тэгээд Ω()
. Дээр дурдсан олон гишүүнт тооцооллын алгоритмуудын хувьд олсон тооцооллыг нэгэн зэрэг хийнэ. O(), Ω()
Тэгээд Θ()
. Дүрмээр бол хамгийн дээд тооцоонд гол анхаарал хандуулсан хэвээр байна O(), тиймээс "сайжруулалтыг" үл харгалзан 2-р алгоритмыг илүүд үздэг. Тэгэхээр, O()- хамгийн муу оролтын өгөгдөл дээр алгоритмын асимптотик үнэлгээ; Ω()
- хамгийн сайн оролтын өгөгдөл дээр, Θ()
- ижил төстэй товчилсон тэмдэглэгээ O()Тэгээд Ω()
. Асимптотик тэмдэглэгээ Хэрэв функцийн хувьд Т(n) тогтмол байдаг в 1 > 0 ба в 2 > 0 гэх мэт тоо n 0 > 0 нөхцөл хангагдсан бол алгоритмын (програмын) гүйцэтгэх хугацаа асимптотын хувьд функцтэй яг тохирч байна гэж бид хэлнэ. n 2. Энэ баримтыг хаана гэж тэмдэглэв n– алгоритмын оролтын урт. Тодорхойлолт 1.
Ер нь эерэг тодорхой функц байгаа бол тэмдэглэгээ нь тогтмол байна гэсэн үг в 1 > 0 ба в 2 > 0 гэх мэт n 0 > 0, энэ нь бүгдэд зориулагдсан. ("" гэсэн оруулгыг "en-ээс ef, en-ээс ижилхэн тета" гэж уншина). Хэрэв тийм бол тэд тийм гэж хэлдэг асимптотын хувьд нарийн тооцоолол(асимптотын нягт хязгаарлагдмал) -ийн хувьд. Үнэн хэрэгтээ энэ хамаарал нь тэгш хэмтэй, хэрэв: , тэгвэл . Цагаан будаа. 2. Тодорхойлолтод зориулсан зураг байгааг анхаарна уу тэмдэглэгээхоёр функцийн хооронд ямар нэгэн хамаарлын баримт, тиймээс хэрэв , мөн тиймийн тул , тогтоогдвол энэ нь огтхон ч гэсэн үг биш юм. Функцийн тэгш хэмийн шинж чанарыг тайлбарлая. Үүнийг харуулж болно. Тодорхойлолтын дагуу эерэг тогтмолуудыг зааж өгөх ёстой 1-ээс, 2-оосболон тоо n 0Ингэснээр тэгш бус байдал хүн бүрт зориулж хийсэн. Тэгш бус байдлын бүх хэсгийг хувааж үзье n 2: Хоёр дахь тэгш бус байдлыг хангахын тулд үүнийг тогтооход хангалттай гэдгийг харж болно в 2 = 1/2. Эхнийх нь хэрэгжих болно, хэрэв (жишээ нь) n 0 = 7 ба в 1 =1/14. Үнэхээр ийм байгаасай гэдгийг харуулъя в 2 ба n 0, энэ нь хүн бүрт зориулагдсан. Харин дараа нь хүн бүрийн хувьд, үүнээс энэ нь дараах в 2 нь тогтмол байх боломжгүй, учир нь энэ нь өсөх тусам нэмэгддэг n, энэ нь тодорхойлолттой зөрчилдөж байна. Аргументийн хангалттай том утгуудын хувьд тэгээс эерэг тогтмолоор тусгаарлагдсан хязгаарлагдмал функцийг илэрхийлдэг -тэмдэглэгээг ашиглах чухал онцгой тохиолдлыг дурдъя. Томъёоны дотор асимптотик тэмдэглэгээг ихэвчлэн ашигладаг. Жишээлбэл, хэлбэрийн давтагдах хамаарал урттай оролтын алгоритмын гүйцэтгэх хугацаа гэсэн үг n(-ын оролтын дарааллын гүйцэтгэлийн хугацаагаар тодорхойлогддог. n–1) элементүүд болон зарим функцууд, тэдгээрийн талаар зөвхөн бидний хувьд үүнээс дутахгүй гэдгийг мэдэх нь чухал юм c 1 nба түүнээс дээш биш c 2 nзарим нэг эерэг 1-ээсТэгээд 2-оосмөн хүн бүрт хангалттай том n, үүнийг тодорхойлолтоор нь . Өөрөөр хэлбэл, оролтын урт өөрчлөгдөхөд програмын ажиллах хугацаа пропорциональ хэмжээгээр нэмэгддэг n, мөн алгоритмын хувьд илэрхийлэл дэх энэ нэр томъёо нь асимптот үнэлгээтэй фрагменттэй тохирч байна. n. Ихэнхдээ асимптотик тэмдэглэгээг албан ёсоор ашигладаггүй, гэхдээ тэдгээрийн зорилго нь контекстээс тодорхой байдаг. Асимптотик тэмдэглэгээний албан бус хэрэглээний ердийн жишээ бол хэлбэрийн тэгш байдлын хэлхээ юм. Эдгээр тэгшитгэлийн хоёр дахь нь дараах байдлаар ойлгогддог: зүүн талд байгаа функц ямар ч байсан нийлбэр нь . Нийлбэрийн асимптотын нарийн тооцоог хайж олоход бид бага эрэмбийн нөхцлүүдийг хасаж болно. nүндсэн нэр томъёотой харьцуулахад жижиг болно. Тэргүүлэх нэр томъёоны коэффициент нь үүрэг гүйцэтгэдэггүй гэдгийг анхаарна уу (энэ нь зөвхөн тогтмолуудын сонголтод нөлөөлж болно -тай 1 ба -тай 2). Жишээлбэл, квадрат функцийг авч үзье, хаана a, b, c– зарим тогтмол ба a > 0.
Доод захиалгын нөхцлүүд болон хамгийн өндөр хугацааны коэффициентээс татгалзаж, бид үүнийг албан ёсоор баталгаажуулахын тулд дараах зүйлийг хийж болно. -тай 1 =a/ 4, в 2 =
7а/ 4i. Ерөнхийдөө аливаа олон гишүүнтийн хувьд p(n)градус гэерэг тэргүүлэх коэффициенттэй бид . 1.3.2 - ба - тэмдэглэгээ Ерөнхийдөө рекорд нь дээд ба доод гэсэн хоёр тооцоог агуулдаг. Тэдгээрийг хувааж болно: Тодорхойлолт 2. Аргументийн хангалттай том утгуудын хувьд сөрөг бус утгыг авдаг функцүүд байг. Ийм тогтмол байдаг бол гэж хэлдэг в> 0 гэх мэт тоо n 0, энэ нь хүн бүрт зориулагдсан (Зураг 3a). Тодорхойлолт 3. Ийм тогтмол байдаг бол гэж хэлдэг в> 0 гэх мэт тоо n 0, энэ нь хүн бүрт зориулагдсан (Зураг 3б). Эдгээр оруулгуудыг дараах байдлаар уншина: “en-ээс ef нь en-ээс o том байна, en-ээс ef-ээс ижил байна,” “en-ээс ef-ээс ижил-ээс омега том байна.” Теорем 1.Аливаа хоёр функцийн хувьд Тэгээд үл хөдлөх хөрөнгө нь зөвхөн болон . Сэтгэгдэл:Аливаа хоёр функцийн хувьд Тэгээд өмчТэгээд тэнцүү байна. (а) (б) Томъёоны дотор асимптот тэмдэглэгээг ашиглаж болно. Жишээлбэл, бид илэрхийлэл бичиж болно хэмжээ гэсэн үг h(1) + h(2) + … + цаг(n), Хаана h(×) – үүнд зориулагдсан зарим функц h(би)=О(би). Энэ нийлбэр нь өөрөө функц болохыг харуулж болно nБайна O(n 2). 1.3.3 болон тэмдэглэгээ Бичлэг нь өсөлттэй байгаа гэсэн үг юм nхарилцаа хязгаарлагдмал хэвээр байна. Түүнээс биш бол дараа нь бид бичнэ ("en-ээс ef-ээс o жижиг-ээс ижил"-ийг уншина). Албан ёсоор хэлэхэд эерэг болгонд n 0 байвал бүгдэд нь . Тиймээс тэмдэглэгээ нь хангалттай том бол сөрөг биш гэж үздэг n. Ойролцоогоор Тэмдэглэгээг үүнтэй төстэй байдлаар оруулсан: хэрэв эерэг байвал ("en-ээс ef-ээс омега жижиг"), хэрэв эерэг байвал байна гэж хэлдэг. дийм зүйл байдаг n 0, энэ нь хүн бүрт, мөн Энэ нь тэнцүү байх нь ойлгомжтой Ойролцоогоор Тиймээс гурван үндсэн тохиолдол байж болно (хязгаарлалт байхгүй дөрөв дэх тохиолдол бас байдаг, гэхдээ алгоритмыг шинжлэх бодит практикт энэ нь маш ховор тохиолддог): Гэсэн хэдий ч практик дээр хатуу тодорхойлолтыг бараг ашигладаггүй. Энэ үнэлгээг хийх илүү тохиромжтой арга байдаг бөгөөд энэ нь авч үзэж буй хоёр функцийн харьцааны хязгаарыг тооцоолоход тусгайлан бүтээсэн хүчирхэг математикийн аппарат, ялангуяа L'Hopital дүрэм юм. болон хангалттай том Стирлингийн томъёо n: Жишээ 1. Функцийн өсөлтийн дарааллыг харьцуул е(n)=n(n– 1)/2 ба g(n)=n 2 . Шийдэл: учир нь хязгаар нь эерэг тогтмолтой тэнцүү, хоёр функц нь ижил өсөлтийн дарааллаар бичигдсэн байдаг. Жишээ 2. Функцийн өсөлтийн дарааллыг харьцуулах ба . Хязгаар нь тэг тул функц нь -ээс бага өсөлттэй байна. Тэр бол . Жишээ 3.Функцийн өсөлтийн дарааллыг харьцуулах ба . Шийдэл: Стерлингийн томъёог ашиглан бид дараахь зүйлийг олж авна. Иймд функц нь маш хурдан өсдөг ч гэсэн функц нь бүр ч хурдан өсдөг бөгөөд үүнийг гэж бичдэг. Тэмдэглэгээний энэ хэлбэрийг ашиглахдаа хязгаарыг ашиглахаас ялгаатай нь функцийн өсөлтийн дараалал нь функцээс өндөр, үүнтэй тэнцүү биш, "том" гэсэн хоёрдмол утгагүй дүгнэлт хийж чадахгүй гэдгийг анхаарна уу. ” омега хэрэглэдэг.
h(51) = h(49) = h(63) = i
P n (x) = a n x n + a n-1 x n-1 + ... + a i x i + ... + a 1 x 1 + a 0
P n (x) = a 0 + x(a 1 + x(a 2 + ... (a i + .. x(a n-1 + a n x)))).
P 3 (x) = a 3 x 3 + a 2 x 2 + a 1 x 1 + a 0 = a 0 + x(a 1 + x(a 2 + a 3 x))
1
0
0
1
16
4
64
256
256
8
2,048
65,536
4,096
12
49,152
16,777,216
65,536
16
1,048,565
4,294,967,296
1,048,576
20
20,969,520
1,099,301,922,576
16,775,616
24
402,614,784
281,421,292,179,456
Өөрөөр хэлбэл, хэрэв програмд нэг функц, жишээлбэл, үржүүлэх функцийг гүйцэтгэдэг O(n)удаа, нэмэлт - O(n 2)удаа, дараа нь хөтөлбөрийн нийт нарийн төвөгтэй O(n 2), эцсийн эцэст нэмэгдэхийн хэрээр nилүү хурдан (тодорхой үед тогтмололон удаа) нэмэлтүүд маш олон удаа хийгдэх тул удаан боловч ховор үржүүлгээс илүү гүйцэтгэлд нөлөөлөх болно. Тэмдэг O()харуулж байна онцгой
асимптотик!
Нэг алгоритм нь 2500n + 1000 үйлдэл, нөгөө нь 2n+1 үйлдэл хийцгээе. Тэд хоёулаа рейтингтэй O(n), тэдгээрийн гүйцэтгэлийн хугацаа шугаман ургадаг тул.
Үүний шалтгаан нь маш энгийн. Бидэнд байг O(log2n). Гэхдээ log 2 n=log 3 n/log 3 2, А бүртгэл 3 2, аливаа тогтмол шиг асимптотик нь тэмдэг юм ТУХАЙ()тооцдоггүй. Тиймээс, O(log2n) = O(лог 3n).
O(g)- олон функц е, ийм тогтмолууд байдаг CТэгээд Н, Юу |f(x)|<= C|g(x)|
бүгдэд нь x>Н.
Бичлэг f = O(g)шууд утгаараа тэр гэсэн үг ебагцад хамаарна O(g). Энэ тохиолдолд урвуу илэрхийлэл O(g) = fутгагүй.
... Оноо байхад f(n) = O(n 3)хамгийн муу тохиолдолд эмх цэгцтэй байх баталгаа болно n 3, их биш.
Θ(n 2)нь нэгэн зэрэг дээд ба доод асимптотик тооцоолол юм - энэ нь үргэлж дарааллаар байх болно n 2үйл ажиллагаа. Зэрэг Θ()
үед л байдаг O()Тэгээд Ω()
давхцаж, тэдгээртэй тэнцүү байна.
Хэрэв бид шалгах эхний алгоритм дээр нэмбэл x=0экспонентациар, дараа нь хамгийн амжилттай анхны өгөгдөл дээр (хэзээ x=0) бидэнд захиалга байна nшалгах, 0 үржүүлэх, 1 нэмэх, шинэ тооцоолол өгөх Ω(n)хуучинтайгаа хамт O(n 2).
Цагаан будаа. 3. Функцийн дээд (а) ба доод (б) асимптотик тооцоо