举例 T(n)=O(1 T(n)=o(log2n) Temp=i; i=j; j=temp |= while(<=n) T(n=o(n) T(n)=O(n2) a=0 for(=1<n;++) b=1 for(=1<=n;i++) y=y+1; for(=0j<=(2^n)j++) s=a+b X+十 b=a a=s
举例 T(n)=O(1) Temp=i; i=j; j=temp; T(n)= O(log2n) i=1; while (i<=n) i=i*2; T(n)=O(n2 ) for (i=1;i<n;i++) { y=y+1; for (j=0;j<=(2*n);j++) x++; } T(n)=O(n) a=0; b=1; for (i=1;i<=n;i++) { s=a+b; b=a; a=s; }
常见的时间复杂度 平方阶o(m2), >常数阶O(1) k次方阶O(m) 对数阶o(og2) 指数阶O(2) >线性阶o(n), >阶乘阶o(n!) 线性对数阶o(nog2n O(1)<0(ogn)cO(n)O(nlogn)<O(n<O(n)O(2") O2") o(n logn o(n) Odon) 图23-1随着规模n的增大,函数的增长趋势
常见的时间复杂 度 ➢ 常数阶O(1) ➢ 对数阶O(log 2 n ) ➢ 线性阶O(n), ➢ 线性对数阶O(nlog 2 n ) ➢ 平方阶O( n 2 ) ， ➢ k次方阶O( n k ) ➢ 指数阶O( 2 n ) ➢ 阶乘阶O(n ！ )
复杂度估计 >最坏情况下的时间复杂度 平均情况下的时间复杂度 >除非特别指定,都是最坏情况的复杂度
复杂度估计 ➢ 最坏情况下的时间复杂度 ➢ 平均情况下的时间复杂度 ➢ 除非特别指定，都是最坏情况的复杂度
算法效率 ■算法空间复杂度 ≯算法的空间复杂度S(η)定义为该算法所耗费的存储空间,它也是 问题规模η的函数。渐近空间复杂度也常常简称为空间复杂度。 ≯一个算法在计算机存储器上所占用的存储空间,包括存储算法本 身所占用的存储空间,算法的输入输出数据所占用的存储空间和算 法在运行过程中临时占用的存储空间这三个方面。算法的空间复杂 度S(η)算法是对一个算法在运行过程中临时占用存储空间大小的量 度
一、算法效率 ◼ 算法空间复杂度 ➢算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是 问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。 ➢一个算法在计算机存储器上所占用的存储空间，包括存储算法本 身所占用的存储空间，算法的输入输出数据所占用的存储空间和算 法在运行过程中临时占用的存储空间这三个方面。算法的空间复杂 度S(n)算法是对一个算法在运行过程中临时占用存储空间大小的量 度
二、查找算法 查找检索:在一组数据中找出满足某种条件的数据的过程 ■线性查找法 int FindF irstUpperLetter( char* string for(i=0; i< strlen(string); 1++ if (isUpper(stringl))return i return -1
二、查找算法 ◼ 线性查找法 ◼ 二分查找法 查找/检索：在一组数据中找出满足某种条件的数据的过程 int FindFirstUpperLetter( char * string ) { int i; for ( i = 0; i < strlen(string); i++ ) if ( isUpper(string[i]) ) return i; return -1; }