算法效率 ■算法时间复杂度 int n =100. sum ∥|行1次 sum=(n+1)*n/2;∥执行1次 执行2n+3次 printf(%d",sum);∥.行1次
一、算法效率 ◼ 算法时间复杂度 int n = 100, sum; //执行 1 次 sum = (n + 1)*n / 2; //执行 1 次 printf("%d", sum); //执行 1 次 执行 2n+3次
算法效率 ■算法时间复杂度 ti,j,X=0,sum=0,n=100 for(i=1; i<=n; i++) for =1; j<=n; j++) n*n X+t sum=sum X printf( %d", sum)
一、算法效率 ◼ 算法时间复杂度 int i, j, x = 0, sum = 0, n = 100; for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) { x++; sum = sum + x; } printf("%d", sum); n*n
算法效率 ■算法时间复杂度 不同算法的操作数量对比 120 100 操作数量 000 0 12345678910 输入规模 分析个算法的运行时间→把操作数量与输入规 模关联起来 >s随着n的增加,nn的执行次数也将远远多于 n的执行次数
一、算法效率 ◼ 算法时间复杂度 ➢ 分析一个算法的运行时间 ➔把操作数量与输入规 模关联起来 ➢ s随着n的增加，n*n的执行次数也将远远多于 n的执行次数 输入规模 操 作 数 量 不同算法的操作数量对比
算法时间复杂度分析 选取算法中一种基本/主要的原操作(多数情 况下取自最深层次循环体内的语句) 以其重复执行的次数T(n)衡量算法运行时间 n是算法处理的数据问题的规模
算法时间复杂度分析 ◼ 选取算法中一种基本/主要的原操作（多数情 况下取自最深层次循环体内的语句） ◼ 以其重复执行的次数T(n)衡量算法运行时间 ◼ n是算法处理的数据/问题的规模
算法时间复杂度分析 如果存在某个存在2个常数:c1,c2,和函数fn) ,使得当问题的规模n→无穷大的时候,有: c1*f(n<t(n<c2*f(n) 那么称T(n)和f(n)具有相同的渐进复杂度,记作 T(n=o( fn))
算法时间复杂度分析 如果存在某个存在2个常数：c1, c2，和函数f(n) ，使得当问题的规模n→无穷大的时候，有： c1*f(n) < T(n) < c2*f(n) 那么称T(n) 和f(n)具有相同的渐进复杂度，记作 T(n) = O( f(n) )