一个算法的『计算量』该如何量化?
发布网友
发布时间：2022-03-29 10:55
共1个回答
热心网友
时间：2022-03-29 12:24
这问题提的好。衡量算法开销通常使用O()运算符由于同一个算法运行于不同的机器上所耗费的实际时间是不同的,所以不能使用实际时间单位衡量算法运行效率,而应使用逻辑单位。描述算法复杂度的参数为算法的输入数据规模,通常用n来表示,那么算法的复杂度可表示为一个关于n的函数。通常最常用的描述算法复杂度的符号为O符号,即将复杂度表示为O(f(n))。其中f(n)用函数形式描述算法执行命令条数与输入规模n的关系,而O()起到估算化简的作用。比如某个算法经过逻辑分析后,其指令数可表示为f(n)=8n^2+10n+500,那么可以使用O(f(n))来简化其表达,O()符号运算性质有多条,总体来说就是保留增长率最高的项且忽略常数系数,上面的表达式化简结果为O(n^2)。当然O()符号不能完美描述算法开销,因为它忽略了常数的影响,当某些项前的常数系数非常非常大时,会对算法复杂度的判断造成误差,这就要具体问题具体分析了。下面简单说一下具体如何分析。for (i = 0;ik *= i;}这段代码每次循环中执行一次乘法两次赋值(假定乘法使用单周期乘法器实现),循环开始执行一次赋值,那么共计执行指令数3n+1,即复杂度为O(n)。for (i = 0;ifor (j = 0;jk += i * j;}循环嵌套时,内层循环执行3n+1条指令,外层循环n次,共n*(3n+1)+1=3n^2 + n +1条指令,即O(n^2)。
