2007/05/08 | 有关算法的时间复杂度
类别(计算机与编程) | 评论(0) | 阅读(214) | 发表于 13:01

算法的工作量用算法所执行的基本运算次数来度量,而算法所执行的基本运算次数是问题规模的函数,即算法的工作量 = f (n)
其中n是问题的规模。例如,两个n阶矩阵相乘所需要的基本运算(即两个实数的乘法)次数为n;即计算工作量为n;也就是时间复杂度为n3。

请问为什么是N的3次方

N的3次方是指这里举的例子:“两个n阶矩阵相乘”而言。
它说,这个问题的“规模”等于矩阵的阶数n。
两个n阶矩阵相乘的基本运算(两个实数的乘法)次数正好是阶数的三次方。f (n) = n ^ 3

别的算法的时间复杂度 = 算法的工作量 = f (n)
f (n) 是什么,要看算什么,怎么算,才知道。未必是N的3次方。

0

评论Comments

日志分类
首页[666]
计算机与编程[133]
EMU[40]
UFOs[24]
房产[127]
音乐[13]
LOG[0]
经济[120]
影视[3]
物理[7]
数学[8]
社会[105]
职场[9]
生物医学[18]
生活[59]