Информатиканың іргелі негіздері
Алгоритмдердің тиімділігі және күрделілігіне талдау жасау
жүктеу/скачать 1,13 Mb.
|
Информатиканы іргелі негіздері
- Бұл бет үшін навигация:
- Анықтама.
| Алгоритмдердің тиімділігі және күрделілігіне талдау жасау.
Бір есепті шешу үшін тек жалғыз алгоритм емес бірнеше алгоритм құруға болатыны белгілі. Сондықтан есепті шешу үшін барлық алгоритмдердің ішінен ең тиімдісін құру қажет болады. Алгоритмді орындаушы-адам болған жағдайда алгоритмнің күрделігі логикамен байланысты, себебі, есепке құрылған алгоритмнің ішінде күрделі структура болса, одан қандай нәтиже алынатынын алдын ала болжау мүмкін емес, тек оны орындап болған соң нәтиженің дұрыстығы, бұрыстығы зерттеледі, ал орындаушы-машина болса, оған алгоритмнің структурасы қаншалықты күрделі екендігі әсер етпейді, себебі машина үшін белгілі нұсқаулар берілді, ол соны орындайды, мысалы: машинаға бәрібір – қосуды орындап жатыр ма азайтуды орындап жатыр ма, әйтеуір техникалық жабдығы дұрыс болса, алдына қойған проблема шешіледі. Немесе алгоритмді жазғанда қайталану операторын қолданбай ақ күрделі есепті шешудің өте көп қадамнан тұратын тізбекті структурасын қолдануға болады, ал машинаға бәрібір- циклды қолдандың ба, тізбекті қолдандың ба, бірақ есептеу уақыты, алынған нәтиже адамды қанағаттандырмауы мүмкін, сондықтан алгоритмнің күрделілігі деген ұғым қажеттілігі шығады. Анықтама. Алгоритмнен туындаған есептеу процесі деп осы алгоритмді орындау барысында өткен тізбекті қадамдар алгоритмін айтады. Анықтама. Алгоритмнің күрделілігі – осы алгоритмді есептеу процесінде қолданылған элементарлы қадамдар саны. Анықтама. Алгоритмнің уақытша күрделілігі – оны орындауға қажетті Т уақыты. Ол элементарлы әрекеттер саны мен оны орындауға кеткен орташа уақыттың көбейтіндісіне тең:T=kt. t- уақыт орындаушы – машинадан тәуелді болса, алгоритмнің күрделілігі k-элементарлы әрекеттер тізбегінің санынан тәуелді. А алгоритмі бар болсын. Оған деректерді өңдеу көлемін көрсететін а параметрі табылсын. Оны (а) – есептің өлшемі дейді. Т арқылы алгоритмнің орындалу уақытын белгілесе, / -арқылы әлдебір n-нан тәуелді функцияны белгілейік. Анықтама. T(n) алгоритмінің өсу реті f(n) бар, немесе басқаша, алгоритмнің теориялық күрделілігі O*(f(n)) бар болады, егер c1, c2>0 тұрақтылары және барлық n<=n0 үшін c1 f(n) Шама дегеніміз есепті шығару барысында қолданылатын белгілеулер. Олар 3 топқа бөлінеді: жүктеу/скачать 1,13 Mb. Достарыңызбен бөлісу:
|