算法的时间复杂度解释

算法的时间复杂度分析有两种方式。
一种方式是计算算法具体的执行时间，最终根据这个时间的长短评价算法的优劣。这种估计方法比较简单易
于操作，但是这种方法有一个缺点：估计时间会随着计算机的不同而产生变化（不同计算机的配置、同一个
计算机所处环境不同都会影响）。
另一种方式是只记录算法的关键操作。


例如这个程序：
--------------------------------------------
for (int a = 0; a < num1; a++)
{
for (int b = 0; b < num2; b++)
{
num[a][b] = b;
}
}
--------------------------------------------
其代码段中出现了循环语句的嵌套。应该使用乘法法则，所以O(T(n))=O(num1*num2)。


循环语句的循环条件会对我们计算算法时间复杂度产生一定的迷惑作用。很多初学者认为循环次数越少的
算法在时间开销方面越小。从原理上说这是对的但不要忘记，大O表示法只是算法在时间开销方面的数量
级，若数量级相同，即使两个算法执行关键操作的步数实际上并不相同，那么也把它们看做是时间复杂度
相等的两个算法。
举例下面的程序：
--------------------------------------------
for (int a = 0; a < num1/2; a++)
{
for (int b = 0; b < num2/2; b++)
{
num[a][b] = b;
}
}
---------------------------------------------
这段代码与前面的例子在结构上一模一样，唯一不同之处在于两重循环的次数减少为原来的一半。用公式
计算这段代码的时间复杂度可知O(T(n))=O(num1*num2/4),显然num1*num2与num1*num2/4具有相同的数量级
两者均为n的平方，所以这段代码与上面的代码具有相同的时间复杂度。


例：
---------------------------------------------
Node* Find(const Type& X, Node* ptr)
{
if (ptr == NULL)
{
return NULL;
}
else
if (X < ptr->data)
return Find(X, ptr->leftChild);
else
if (X > ptr->data)
return Find(X, ptr->rightChild);
else
return ptr;
}
--------------------------------------------
上述代码定义了函数Find。但在实现部分函数又调用了Find自身。
像这种自身定义自身的情况就叫做递归。
函数Find的作用是在指针ptr指向的链表中寻找变量X，并返回指向X所在结点的指针。这里链表中的数是有
序存放的，现假定它为从小到大的顺序。Find的执行过程是：首先令X与链表中间的数值进行比较，若相等
，返回结点指针；若小于，则在中间结点左侧的链表中寻找变量X，寻找方式与上面相同；若大于，则在中
间结点的右侧链表中寻找变量X，寻找方式与上面相同。如此递归下去直到算法结束为止。（折半查找法）
这是一种常用的查找法。
若链表的长度为n，则平均查找的时间为log以2为底n的对数，所以算法的时间复杂度为O(log@2n)。




通常程序的时间复杂度有（按照从小到大的顺序排列）：c, log@2n, n, nlog@2n, n^2, n^3, 2^n,
3^n, n!。（@表示以2为底，n^2表示n的2次方）
若c表示常数，即算法的执行时间是固定不变的，不随程序中其他变量状态的改变而发生变化。但要注意，
语句a=1;与语句a=(a+b)*c+(d+e)*f+g/h;的时间复杂度同为c。不可认为后面的赋值语句较长就认为它有更
高的时间复杂度。