«Информатиканың теориялық негіздері»



бет53/80
Дата25.12.2021
өлшемі0,68 Mb.
#105341
1   ...   49   50   51   52   53   54   55   56   ...   80
Байланысты:
«Информатиканы теориялы негіздері»

Есептеу күрделілігі. Тиімділік анализі кей жағдайда ғана мүмкін болады. Айталық, массив элементтер саны n=2 (K=log2n) 1-сканерлеуде n-1 салыстыру жүргізіледі. Оның нәтижесінің өлшемі өлшемді ішкі тізім пайда болады. Өңдеудің келесі фазасында әрбір ішкі тізім үшін n/2 салыстыру қажет болады. Осылайша, бөлу процесі табылған ішкі тізімдер тек бір ғана элементтер тұрғанша К жүрістен кейін аяқталады. Мұндағы салыстырулардың жалпы саны мына формуламен анықталады: n*k=n*log2n. Жалпы түрдегі тізім үшін есептеу күрделілігі – О(n log2n) тең болады. Ал ең нашар жағдайда орталық элемент ең кіші элемент болғанда есептеу күрделігі O(n2) тең болады.



Достарыңызбен бөлісу:
1   ...   49   50   51   52   53   54   55   56   ...   80




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет