算法的工作量用算法所执行的基本运算次数来度量,而算法所执行的基本运算次数是问题规模的函数,即算法的工作量 = f (n)
其中n是问题的规模。例如,两个n阶矩阵相乘所需要的基本运算(即两个实数的乘法)次数为n;即计算工作量为n;也就是时间复杂度为n3。
请问为什么是N的3次方
N的3次方是指这里举的例子:“两个n阶矩阵相乘”而言。
它说,这个问题的“规模”等于矩阵的阶数n。
两个n阶矩阵相乘的基本运算(两个实数的乘法)次数正好是阶数的三次方。f (n) = n ^ 3
别的算法的时间复杂度 = 算法的工作量 = f (n)
f (n) 是什么,要看算什么,怎么算,才知道。未必是N的3次方。