Кіріспе
Компьютерде белгілі бір мәселені шешу үшін қажетті нәрсе, мысалы, өңдеу қадамдары немесе жад. Есептеу күрделілігі теориясында, есептеу ресурсы – есептеу модельдерінің есептеу мәселелерін шешуде пайдаланатын ресурсы. Ең қарапайым есептеу ресурстары – есептеу уақыты, мәселені шешу үшін қажетті қадамдар саны және жад кеңістігі, мәселені шешу кезінде қажетті сақтау көлемі, бірақ одан да күрделі көптеген ресурстар анықталған. Есептеу мәселесі әдетте, кез келген жарамды кіріс дерегіне қатысты әрекеті арқылы анықталады. Мәселелердің мысалдары: "n бүтін санын беріп, n-нің жай сан екенін анықтау" немесе "x және y екі санды беріп, x*y көбейтіндісін есептеу" болуы мүмкін. Кіріс дерегінің көлемі ұлғайған сайын, мәселені шешу үшін қажетті есептеу ресурстарының саны да артады. Сондықтан, мәселені шешу үшін қажетті ресурстар асимптотикалық талдау арқылы сипатталады, ресурстар кіріс дерегінің ұзындығы мен мөлшеріне байланысты функция ретінде анықталады. Ресурстарды пайдалану көбінесе Big O белгісі арқылы ішінара мөлшерленеді. Есептеу ресурстары пайдалы, себебі біз әрбір есептеу ресурсының белгілі бір мөлшерінде қандай мәселелерді шешуге болатынын зерттей аламыз. Осылайша, біз мәселені шешу алгоритмдерінің оңтайлы екенін анықтап, алгоритмнің тиімділігі туралы тұжырым жасай аламыз. Белгілі бір есептеу ресурсының белгілі бір мөлшерін пайдалану арқылы шешілетін барлық есептеу мәселелерінің жиынтығы – күрделілік класы, ал әртүрлі күрделілік кластары арасындағы қатынастар күрделілік теориясының ең маңызды тақырыптарының бірі болып табылады.
In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems. The simplest computational resources are computation time, the number of steps necessary to solve a problem, and memory space, the amount of storage needed while solving the problem, but many more complicated resources have been defined. A computational problem is generally defined in terms of its action on any valid input. Examples of problems might be "given an integer n, determine whether n is prime", or "given two numbers x and y, calculate the product x*y". As the inputs get bigger, the amount of computational resources needed to solve a problem will increase. Thus, the resources needed to solve a problem are described in terms of asymptotic analysis, by identifying the resources as a function of the length or size of the input. Resource usage is often partially quantified using Big O notation. Computational resources are useful because we can study which problems can be computed in a certain amount of each computational resource. In this way, we can determine whether algorithms for solving the problem are optimal and we can make statements about an algorithm's efficiency. The set of all of the computational problems that can be solved using a certain amount of a certain computational resource is a complexity class, and relationships between different complexity classes are one of the most important topics in complexity theory.
Жалпы қолжетімді есептеу техникасын сипаттау
"Есептеу ресурсы" термині көбінесе қолжетімді есептеу техникасы мен бағдарламалық қамтамасыздау үшін қолданылады. Пайдалы есептеулерді қараңыз.
Есептеу қабілетін ресми түрде өлшеу
Есептеу мүмкіндігін ресми түрде сандықпен өлшеуге белгілі бір күш-жігер жұмсалды. Белгілі бір есептеулерді модельдеу үшін, нақты мәселені шешуге қажетті есептеу күшін сандықпен бағалау мақсатында, шектелген Тьюринг машинасы күйлердің өту саны мен әліпби мөлшерін пайдаланылды.