Төвөгшилт буюу хүндрэл /complexity/

Том О тэмдэглэгээний тухай

Математикт том О тэмдэглэгээ нь энгийн функцуудад хэрэглэгдэх ба функцын аргумент нь онцгой утга эсвэл төгсгөлгүйрүүгээ тэмүүлэх үед уг функцын хязгаарын шинж чанарыг дүрслэхэд хэрэглэгддэг. Үүнийг заримдаа Landau тэмдэглэгээ, асимптотик тэмдэглэгээ ч гэж нэрлэдэг. Компьютерийн шинжлэх ухаанд, алгоритмын үр ашгийг том О – оор тэмдэглэн ялгадаг. Аналитик тоон онолд энэ нь арифметикийн функцын асимптотик дундаж хэмжээ эсвэл асимптотик хэмжээг их утгатай төгсгөлөг аргумент авсан дундаж утга эсвэл ямар нэгэн утгаар солих үед гарах “Баталгаажсан алдаа”-г тооцоолоход хэрэглэнэ. Ижил өсөлттэй боловч өөр өөр функцууд ижил О тэмдэглэгээг хэрэглэх учир том О тэмдэглэгээ нь тэдний өсөлтийн функцаар дүрслэгддэг. Тиймээс функцын эрэмбэ буюу дарааллыг О (Order of function) гэж тэмдэглэдэг юм.

Юм бүхэн хялбар биш ч боломжоороо л энгийн байх хэрэгтэй шдээ. 

Complexity-төвөгшилт /хүндрэл/

Хугацааны төвөгшилт (Time complexity)

Хамгийн багыг хайж ангилах алгоритм дээр жишээ авья. Энэ алгоритм үйлдлийг гүйцэтгэж дуусахад хэдий хэмжээний хугацаа зарцуулах бол? Магадгүй оролтын хэмжээнээс хамаарч их бага хугацаа зарцуулах байх л даа. Заримдаа программыг эхлүүлэхээс өмнө ажиллах хугацааг тооцоолох боломжтой байдаг. Жишээ нь хотын бүх утасны жагсаалтыг бага тооноос нь эхлүүлэн ангилж жагсаа гэвэл хэдий хугацаа орохыг хэн ч мэдэхгүй, жилийн турш утасны жагсаалтыг ангилах шаардлагатай ч болж мэднэ. Гарцаагүй тооцоолох цаг (ажиллах цаг) нь ангилагдах хэлхээсийн n тооны хэмжээсээс хамаарна. Өөрөөр хэлбэл 100 тоог ангилна гэвэл оролтын мэдээний тоо n нь 100 болно.

Бид n –ээс хамаарсан ажиллах хугацааг тодорхойлох томьёог бичиж болох болов уу?

Ангилах программд хоёр үүрлэсэн гогцоо байна гэж үзье. Хоёр гогцоо хоёулаа 0 – ээс n хүртэл өөрчлөлтүүдийг авч үзэх боловч дотоод гогцоо нь гадна гогцооны  зогсож байгаа утгаас яг эхлэнэ. Мөн зарим даалгавар болон харьцуулах “хэрэв-if” гэх мэт комманд уг үүрлэсэн гогцоонд оршино. Ажиллах хугацааны хувьд сайн хэмжилт нь харьцуулалтыг гүйцэтгэх тоо юм. Эхний интеграцид /заримдаа итераци гэж нэрлэнэ/ n тооны хэмжигдэхүүнийг хооронд нь харьцуулна. Дараа нь n-1, n-2, n-3 гэх мэтээр буурч сүүлд нь 3, 2, 1 гэх мэтээр дуусна. Тэгэхээр 1+2+3+...............+n тооны харьцуулалт хийнэ гэсэн үг. Гауссын нийлбэрээр энэ нь (1/2)n(n-1) тооны харьцуулалт болно. Үүнийг зургаар харуулбал:

Figure 1. Хамгийн багийг хайж ангилах алгоритмын ажиллах хугацааны дүрслэл

Будагдсан талбай нь бүх харьцуулалтын тоог харуулна. Энэ нь n гэсэн талтай квадратын талбайн хагастай тэнцүү харагдаж байна. Иймд бараг (½)n² гэж бичиж болох юм. Энэ илэрхийллээр хэдий хугацаа шаардлагатайг хэрхэн үнэлэх вэ? Энэ илэрхийлэл сайн эсвэл муу тайлбар өгөхийг хэрхэн яаж мэдэх вэ?

Хэрэв бид давхар хэлхээс ашиглагдана гэж үзвэл ангилалтанд 4 дахин хугацаа зарцуулах нь байна. Хэрэв бид 10 дахин ихэсгэвэл програм дуусах хүртлээ 100=10² дахин хугацаа авна. Энэ бүгд n² гэсэн илэрхийллээс болж байна. Тэгэхээр хамгийн багыг хайж ангилах алгоритм нь квадрат төвөгшилтэй (quadratic complexity) байна гэж хэлж болно.  Энэ нь бидэнд их хэмжээний оролттой үед их хэмжээний хугацаа зарцуулна гэдгийг урьдчилан хэлж байна.

Зарим нэг хөнгөн бодлоор бол бид их мөнгөөр 2 дахин хурдан машин /компьютер/ авбал түүгээрээ оролтуудыг хоёр дахин хурдан ангилж болно гэж эндүүрч болно. Онолоороо бол ажиллах хугацааг авч үзэх нь энэ мэт эндүүрлээс сэргийлж чадна. Програмын гүйцэтгэх үеийн түүний ажиллах хугацааг “хугацааны төвөгшилт” (time complexity) гэж нэрлэдэг. Өөрөөр хэлбэл алгоритмын хугацааны төвөгшилт гэдэг нь оролтоор илэрхийлэгдсэн хэлхээсийн уртын функцыг тодорхойлоход алгоритмд шаардлагдах хугацааг илэрхийлдэг. Энэ тоо нь үндсэндээ алгоритмын оролтын хэмжээнээс хамаарах ба алгоритмыг хэрэглэж ангилагдсан байх хэлхээсний /урт/ тоогоор ойролцоологдоно. Иймд энэ алгоримтын хугацааны төвөгшилт нь c*n² гэсэн илэрхийллээр дүрслэгдэнэ. Өөр алгоримтын хувьд ямар байхыг бодож тодорхойлно. С бол тогтмол тоо байх ба хэрэглэсэн програмчлалын хэл, эмхтгэгчийн (compiler) төрөл, чанар, CPU, үндсэн санах ойн багтаамж, ашиглах хугацаа, програм бичигчийн мэдлэг гэх мэтээс хамаарах ба алгоритмаас асар бага хамаарна. Бидний жишээний хувьд c=1/2 юм. С-г гадаад хүчин зүйлийг /ихэвчлэн мөнгө зарцуулах/ сайжруулсанаар багасгаж болох ба n² гэсэн илэрхийлэл нь өөрчлөгдөхгүй хэвээр байсаар л байна.

Том О

Өөрөөр хэлбэл с нь ажиллах хугацаанд тийм ч чухал бус параметр болж байна. Энэ нөхцөл байдлыг харгалзан үзэж ажиллах хугацааны төвөгшилтийг том О үсгээр тэмдэглэе. Иймд жишээний хувьд ажиллах хугацааны төвөгшилт нь О(n²) байна гэж хэлж болно.

Математик талаас авч үзвэл О(n²) нь функцуудын бүрдлээс тогтох ба эдгээр функцууд нь n² – аас илүү хурдан өсөлттэй байж чадахгүй /удаан хугацаанд ажиллахад/ бөгөөд эдгээр фцнкцуудын хувьд n² нь дээд хүрээ байна гэж хэлж болно. Илүү нарийвчлан харвал дараах үнэн илрэх болно. Функц f нь О(n²) бүрдлийн элемент байх ба ямар нэгэн хүчин зүйл с болон n – тэй тэнцүү эсвэл бага бүхэл тоо n_o нар байна.

Иймд функц n² – ыг f – ийн хувьд асимптотик дээд хүрээ гэнэ. Ерөнхийдөө f(n)=O(g(n)) тэмдэглэгээ нь f функц нь g(n) функцаар дээгүүрээ хүрээлэгдэнэ гэсэн үг юм.  О(n²) – аас f функц нь n² – аас удаанаар их хэмжээгээр өсөж байвал f/n² харьцаа нь n – ийн өсөлттэй үед 0 – рүү тэмүүлнэ. Үүний жишээ нь f(n)=n функц юм. Гэвч энэ нь ангилах алгоритмын ажиллах хугацааг дүрслэх f функцын хувьд хүчингүй юм. Ангилах арга нь n² харьцуулалтын шаарддаг (1/2 гэсэн тогтмолыг тооцохгүй бол). n² нь f – ийн хувьд мөн асимптотик доод хүрээг илтгэнэ. Энэ f нь n² шиг удаан хугацааг илтгэнэ. Математикаар илэрхийлбэл c₁ ба c₂ гэсэн хүчин зүйл мөн n_o гэсэн бүхэл тоонууд гэх мэтийн хувьд бүх n нь n_o  - оос их буюу тэнцүү байна.

Тэгэхээр f нь n² – аар дээд болон доороосоо хүрээлэгдэнэ. Эдгээ функцын хувьд мөн өөрийн гэсэн тэмдэглэгээ Ө(n²)  гэж бий. Дараах зураг нь O(g(n)) – ээр дээгүүрээ хүрээлэгдсэн f функц болон асимптотик шинжийг Ө(g(n))  – ээр дүрсэлсэнийг ялган харуулж байна. Сүүлчийн зураг нь c₁ ба c₂ хүчин зүйлийн үр дүн g(n) – ийн орчин дахь гуурсийг илэрхийлж байна.

Figure 2. Асимптотик хүрээнүүд (О ба Ө)

Бид утгын эрэмбийг тодорхойлж (order of magnitude) чадахаас бус ажиллах хугацааг нарийвчлан тодорхойлох боломжгүй. Яагаад гэвэл с нь олон хүчин зүйлээс хамаарсан ихэвчлэн туршилтаар л тодорхойлогддог коэффициент юм. Ном, өгүүлэл, лавлахуудад тогтмол хугацааны (constant time) төвөгшилтэй гэж тааралдах ба энэ нь тогтмол тоонд машин зааварчилгааг гүйцэтгэгдэнэ гэсэн үг ба оролтын хэмжээнээс үл хамаарна. Иймд ажиллах хугацааг илэрхийлэх  функ нь O(1) гэж тэмдэглэгдэнэ. Мөн шугаман ба логрифм төвөгшилт (linear and logarithmic time) гэдэг нь тус бүр O(n) ба O(log(n)) хугацааг авна гэж тэмдэглэгдэнэ. Цаашилбал тооцоот хугацааны төвөгшилт (expected time) О(g(n)) гэдэг нь гүйцэтгэлээс гүйцэтгэл хооронд ажиллах хугацаа нь өөрчлөгдөх ба тооцоот хугацаа нь асимптотик хүрээ g(n) функцаас хамаарч хүрээлэгдэнэ.

Бид хамгийн багийг хайж ангилах алгоритмыг жишээ болгон авч үзэж байгаа. Тэгвэл мөнгө үрж компьютерийн чадлыг сайжруулахгүйгээр илүү хурдан алгоритмыг хайж олсон гэж үзье. Тэр хурдан алгоритмыг “quicksort” буюу түргэн ангилагч гэж нэрлэе. Энэ алгоримт нь O(n log(n)) гэсэн төвөгшилтэй гэж үзвэл O(n²) – аас хамаагүй дээр харагдаж байгаа нь ойлгомжтой. n бага бол эсрэгээр O(n log(n)) нь O(n²) – аас их төвөгшилтэй болох ба энэ нь түргэн ангилах алгоритм бага хэмжээтэй оролттой үед ашиглахад үр дүнгүй гэдгийг харуулж байна.

Одоо буцаад эхний асуултруу оръё. Бид тодорхой хугацаанд утасны жагсаалтыг ангилж чадах болов уу? Хариулт нь оролтын тоо n (хотын утас хэрэглэгчдийн тоо) болон системтэй холбоотой коэффициент с – ээс л хамаарна.

Орон зайн төвөгшилт (space complexity)

Хугацааны хувьд төвөгшил багатай алгоримт нь практикт ажлыг түргэн гүйцэтгэнэ гэж ойлгож болно. Хугацааны төвөгшилөөс тусдаа орон зайн төвөгшил мөн чухал. Энэ нь алгоритмд хэрэглэгдэх санах ойн багтаамжийн нүдийн /cell/ тоо юм. Сайн алгоритм нь бага орон зай эзлэх ёстой.

Том О тэмдэглэгээг ерөнхийдөө хязгаартай болон хязгааргүй асимптотикт хэрэглэнэ. Хязгаартай асимптотикт бага эрэмбийг орхино. Хязгааргүйд бол хязгааргүй багасах гишүүдийг тэмдэглэнэ.

Сурвалж: Леда-туториал сайтаас.