当前位置 博文首页 > odelia的博客：数据结构-算法-时间复杂度
? ?顾名思义就是该算法运行的时间，什么样的算法算是高效的算法，无外乎是用最少的内存空间，花最短的时间解决问题的算法就是。所以我们考虑用时间和空间来衡量一个算法的效率，我们来看看定义：在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级。记做T（n）=O（f（n））
? ?根据定义，求解算法的时间复杂度的具体步骤是：
? ?1、找出算法中的基本语句；
? ?? ?算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体
? ?2、计算基本语句的执行次数的数量级；
? ?? ?只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数
? ?3、用大O记号表示算法的时间性能
? ?将基本语句执行次数的数量级放到大O记号中
在这里说一下常遇见的几个时间复杂度：
O（1）：常数阶 ? ? ?O（n）：线性阶 ? ?O（n^2）:平方阶
? ?推导规则：
? ?1、用常数1取代运行时间中所有加法常数。
? ?2、其次，只保留最高阶项。
? ?3、如果阶项系数存在且不为1，则去掉这个系数。
? ?最终得到的就是大O阶，简单说就是保留求出数的最高次幂，并且把系数去掉，如：(T)=2n^2+n+1=O(n^2)
<span style="font-family:KaiTi_GB2312;font-size:24px;">int main()
{
int sum = 0, n = 100; /* 执行1次 */
sum = (1 + n) * n/2; /* 执行1次 */
printf("%d", sum); /* 执行1次 */
} </span>? ?分析：算法运行次数的函数f(n)=3,根据上面的推导规则，第一步将3改为1，再保留最高阶项，它没有最高阶项，所以算法时间复杂度应该是O（1），注意：只是用执行次数来衡量时间复杂度，但执行次数并不等于时间复杂度，无论输入规模n为多少，执行时间总是恒定的，时间复杂度总是O（1）
再来看一段代码：
<span style="font-family:KaiTi_GB2312;font-size:24px;">int sum = 0 ; n = 100; /*执行1次*/
sum = (1+n)*n/2; /*执行1次*/
sum = (1+n)*n/2; /*执行1次*/
sum = (1+n)*n/2; /*执行1次*/
sum = (1+n)*n/2; /*执行1次*/
sum = (1+n)*n/2; /*执行1次*/
sum = (1+n)*n/2; /*执行1次*/
sum = (1+n)*n/2; /*执行1次*/
sum = (1+n)*n/2; /*执行1次*/
sum = (1+n)*n/2; /*执行1次*/
sum = (1+n)*n/2; /*执行1次*/
printf("%d",sum); /*执行1次*/</span>? ?此外，对于分支结构而言，无论真假执行的次数都是恒定不变的，不会随着n的变大而发生变化，所以单纯的分支结构（不在循环结构中），其时间复杂度也是O(1)。
<span style="font-family:KaiTi_GB2312;font-size:24px;">int main()
{
int i, sum = 0, n = 100; /* 执行1次 */
for( i = 1; i <= n; i++) /* 执行 n+1 次 */
{
sum = sum + i; /* 执行n次 */
//printf("%d \n", sum);
}
printf("%d", sum); /* 执行1次 */
}
</span>
<span style="font-family:KaiTi_GB2312;font-size:24px;">int i; /* 执行1次 */?
for(i = 0 ; i < n ; i++){ /* 执行n+1次 */?
for(j = 0 ; j < n ; j++){ /* 执行n*（n+1）次 */?
/*时间复杂度为O(1)的程序*/ /* 执行1次 */?
}
}</span>? ? ? ? ? ?
