时间复杂度(Time Complexity)的定义

　　 在程序设计中，决定某程序区段的步骤计数是程序设计师在控制整体程序系统时间的重要因素，不过要决定精确的次数却也真是一困难的工作。特别是在不确定型(如指令x=l和x=x2+x3.15/x-4)比较，虽然我们都将其视为一个指令，不过运用的复杂程度理所当然影响了真正精确的执行时间。由此得知花费很大的功夫去计算真正的执行次数是没有意义的。所以我们往往以一种「概量」的精神来做为衡量的准则，称为「时间复杂度」(Time complexity)。按着我们就来看它的详细介绍:
　　 我们定义一个T(n)，表示在一个完全理想状态的计算器中程序所执行的实际指令次数。一个程序的执行时间并不完全和输入量有关，算法的好坏也会影响，所以我们可以把它当作输入量为n的一种函数。又在此我们可以定义对输入量n而言，它的最大执行时间就是时间复杂度(Time complexity)的衡量标准。通常在渐近表示法(Asymptotic Notation)中，我们一般以Big-oh来表示。

何谓Big-oh?

　　O(f(n))可以看成是某一算法在计算机中所需执行时间始终不会超过某一常数倍的f(n)。更清楚的说就是若某算法的执行时间T(n)的时间复杂度是O(f(n))，意谓存在两个常数c与n0，若n≧n0，则T(n)≦cf(n)。f(n)又可以称为执行时间的成长率(rate of growth)。为了增加同学的了解，我们赶快来看看有关的一些例子。
    例如，假设某些程序详细分析后得到的结果是其运算的次数与参数n有关，如下：N(n)=3n2+11n-45
　　 在这个多项式中会主导整个函式且成长最快的是n2项，一般而言，在一个多项式中会主导的项是具有最高次的那一项。用一个表来说明这个表示式中值的成长是n在主导的，如下的表所示。从这个表我们可以观察到只使用n2项而不是使用整个公式时，它会随着n变大而与正确值的误差百分比会非常小。这主要是因为这个项的成长比其它二个项的成长还要快速，这二个项因此可以被忽略。我们可以说对于较大的n值，这个子程序基本上是一个3n2的处理程序。

例：请问下面程序区段的循环部份实际执行次数及时间复杂度
　for i =1 to n
　for j= i to n
　for k=j to n
　…
　next k
　next j
　next i 
答： 这个问题是希望同学对有关实际执行次数和时间复杂度在表现意义上的不同。在本题有关实际执行次数的问题，同学先要清楚是指那一道指令的次数。由于这题是「循环」执行的部份，毋需考虑循环内部指令的多寡。因此我们可用数学式来计算：
　　这个n(n+l)(n+2)/6就是实际的循环执行次数，且我们知道必定存在c，n0使得n(n+l)(n+2)/6≦cn³，当n≧n0时，时间复杂度为O(n³)