高考问答禁宫情by小十四腐书网:关于时间复杂度的疑惑?!!!!!!!!!!!!!!!!!!!!!!!!!!!!
来源：百度文库 编辑：高考问答 时间：2024/05/01 21:17:02
我在书上看到这段话很不明白>
人们通常采用大O表示法来描述算法分析结果。如果存在正的常数M和n0，当问题的规模n>=n0后，算法的时间量度T(n)=<M*f(n),那么就称该算法的时间复杂度为0(f(n)).这种说法意味着：当n充分大时，该算法的时间复杂度不大于f(n)的一个常数倍。
这里的O和n,n0 T(n) M,等等.这些到底什么意思呀?
最好能给我几个例子
人们通常采用大O表示法来描述算法分析结果。如果存在正的常数M和n0，当问题的规模n>=n0后，算法的时间量度T(n)=<M*f(n),那么就称该算法的时间复杂度为0(f(n)).这种说法意味着：当n充分大时，该算法的时间复杂度不大于f(n)的一个常数倍。
这里的O和n,n0 T(n) M,等等.这些到底什么意思呀?
最好能给我几个例子
O 是时间复杂度，是一个表示程序随机算规模增加而消耗时间增长的函数
n 是指程序规模
n0 是指一个临界点当超过这个临界点的时候O产生作用（也就是说允许在一个较小规模的时候时间不合O发生严格的正相关关系）
T（n）是指规模为n时程序所使用的时间
M 一个常系数
例子
for(int i = 0; i < n; i++)
{
for (int t = 0; t < n; t++)
{
//
操作1；
操作2；
}
}
好了 当n >= 2 时
在模型机上运行的时候 所用的时间就是
1ms(循环里面那两个操作的时间)*2 * n(内层循环)*n（外层循环）
也就是说 T(n) = 2ms *n^2
当然了在具体的时候两个操作所用的时间不一样（比如乘法和加法的指令周期是不一样的），而且循环本身也是要消耗时间。不过分析时间复杂度一般不考虑那么多
当然不管多大的数都是有一个比例的，在这里我们可以估算一下肯定不大于7ms（其实没必要考虑这些）
所以这时
T(n) <= 7ms *n^2
M= 7；
这时候我们不再管操作具体执行时间是多少，直接把常数扔掉，得到
O(n^2)
他的意思是当规模大于1时，随着n的增大，程序的时间会以n^2的速度增加
这不是严格的讨论量的关系，这是在讨论它的增长速度的问题。不知道我说清楚了没有