Алгоритмдер жєне деректер структурасы


Анықтама. Алгоритмнен туындаған есептеу процесі деп осы алгоритмді орындау барысында өткен тізбекті қадамдар алгоритмін айтады. Анықтама



бет13/41
Дата05.09.2020
өлшемі0,89 Mb.
#77252
1   ...   9   10   11   12   13   14   15   16   ...   41
Байланысты:
5bacf48a-311c-11e3-8846-f6d299da70eeУМК-алг (1)

Анықтама. Алгоритмнен туындаған есептеу процесі деп осы алгоритмді орындау барысында өткен тізбекті қадамдар алгоритмін айтады.

Анықтама. Алгоритмнің күрделілігі – осы алгоритмді есептеу процесінде қолданылған элементарлы қадамдар саны.

Анықтама. Алгоритмнің уақытша күрделілігі – оны орындауға қажетті Т уақыты. Ол элементарлы әрекеттер саны мен оны орындауға кеткен орташа уақыттың көбейтіндісіне тең:T=kt.

t- уақыт орындаушы – машинадан тәуелді болса, алгоритмнің күрделілігі k-элементарлы әрекеттер тізбегінің санынан тәуелді.

А алгоритмі бар болсын. Оған деректерді өңдеу көлемін көрсететін а параметрі табылсын. Оны (а) – есептің өлшемі дейді. Т арқылы алгоритмнің орындалу уақытын белгілесе, / -арқылы әлдебір n-нан тәуелді функцияны белгілейік.

Анықтама. T(n) алгоритмінің өсу реті f(n) бар, немесе басқаша, алгоритмнің теориялық күрделілігі O*(f(n)) бар болады, егер c1, c2>0 тұрақтылары және барлық n<=n0 үшін

c1 f(n)2f(n) шарты орындалатындай n0 саны табылса. Мұндағы f(n) функциясы ең болмағанда n<=n0 үшін теріс емес болуы керек. Егер T(n) үшін T(n)<=cf(n) шарты орындалса, онда алгоритмнің теориялық күрделілігі O(n) болады. (n-нен үлкен «0» деп оқылады.).

Шама дегеніміз есепті шығару барысында қолданылатын белгілеулер. Олар 3 топқа бөлінеді:


  1. аргументтер – енетін шамалар

  2. аралық шамалар

  3. нәтижелер – шығатын шамалар



Достарыңызбен бөлісу:
1   ...   9   10   11   12   13   14   15   16   ...   41




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

    Басты бет