时间复杂度
时间复杂度 时间复杂度是计算机科学中的一种概念,用于描述算法的运行时间。它是一个函数,定量描述了该算法的运行时间,并且是关于代表算法输入值的字符串的长度的函数。时间复杂度常用大 O 符号表述,不包括这个函数的低阶项和首项系数。 时间复杂度是指执行算法所需要的计算工作量,它是评估算法效率的重要指标。时间复杂度越低,算法的效率越高。时间复杂度的计算方法为:T(n)=O(f(n)),其中f(n)是模块 n 的某一个函数。 计算时间复杂度的步骤为: 1. 找出算法的基本操作。 2. 根据相应的各语句确定它的执行次数。 3. 找出 T(n) 的同数量级,如 1, log(2)n, n, n log(2)n, n 的平方, n 的三次方, 2 的 n 次方, n!。 4. 找出 f(n) = 该数量级。 5. 若 T(n)/f(n) 求极限可得到一常数 c,则时间复杂度 T(n) = O(f(n))。 例如,算法: ``` for(i=1;i<=n;++i){ for(j=1;j<=n;++j){ c[i][j]=0; for(k=1;k<=n;++k) c[i][j]+=a[i][k]*b[k][j]; } } ``` 则有 T(n) = n 的平方 + n 的三次方,根据同数量级,我们可以确定 n 的三次方 为 T(n)的同数量级,则有 f(n) = n 的三次方,然后根据 T(n)/f(n) 求极限可得到常数 c,则该算法的时间复杂度:T(n) = O(n^3)。 在 pascal 中比较容易理解,容易计算的方法是:看看有几重 for 循环,只有一重则时间复杂度为 O(n),二重则为 O(n^2),依此类推,如果有二分则为 O(logn),二分例如快速幂、二分查找,如果一个 for 循环套一个二分,那么时间复杂度则为 O(nlogn)。 因此,时间复杂度是评估算法效率的重要指标,通过计算时间复杂度,可以知道算法的执行时间,并且可以对算法进行优化,以提高算法的效率。