计算机术语“polynomial complexity”的中英文意思、释义、翻译及用法-计算机英汉双解词典

网站首页词典首页

术语	polynomial complexity
释义	polynomial complexity 多项式复杂性 A means of measuring the resources used during a computation. During any Turing machine computation various resources will be used, e.g. space and time. These can be defined formally as follows: Given a Turing machine program M and input string X, then Time (M,X) is defined as the number of steps in the com putation of M on X before M halts. Time is undefined (i.e. equals infinity) if M does not halt on x. The time complexity of M is defined to be the integer function TM whereTM(n)=max(Time (M,X): \|x \|=n) for nonnegative integer n. Space (M,X) is similarly defined as the number of tape used by M on X, and the space complexity SM is defined by  SM(n)=max (Space (M,X): \|x \|=n) An algorithm for which the complexity measure TM(n) or SM(n) increases with n no more rapidly than a polynomial in n is said to be polynomially complexity. 计算时使用的对资源的一种度量方法。图灵机计算时要使用各种资源,如空间和时间,它们形式上可定义如下:给出一个图灵机程序M和输入串X,M停止之前M对X的计算步数定义为Time(M,X),如M对X执行不停,则时间是不确定的(即等于无限)。M的时间复杂性可用整数函数TM定义: TM(n)=max(Time (M,X): \|x \|=n) 对非负整数n。类似地,M对X计算时用磁带数定义为Space(M,X)。空间复杂性SM可定义如下: SM(n)=max(Space(M,X): \|x \|=n) 对于一个算法,当测量它的TM(n)或SM(n)的复杂性随n的增加不比一个n多项式增加更快时,就说它的复杂性是多项式复杂性。
随便看	Electronic Yellow Pages Files electro-optic detector electrophotograph electroplating electrosensitive paper electrostatic document copying machine electrostatic image electrostatic plotter electrostatic printer electrostatic printing electrostatic process perceptron percolation perfect secrecy perforated tape perforated tape code perforatedtape reader perforations perforator performance evaluation performance objective performance option performance (PERF) performance reference perigee

计算机英汉双解词典包含21137条计算机术语英汉翻译词条，基本涵盖了全部常用计算机术语的翻译及用法，是计算机学习及翻译工作的有利工具。