网站已运行时间代码,网站开源程序,手机网站建设推广方案ppt,教育类网站模板转发:https://blog.csdn.net/LF_2016/article/details/52453212
时间复杂度#xff1a; 一般情况下#xff0c;算法中基本操作重复执行的次数是问题规模n的某个函数f(n)#xff0c;进而分析f(n)随n的变化情况并确定T(n)的数量级。这里用O来表示数量级#xff…转发:https://blog.csdn.net/LF_2016/article/details/52453212
时间复杂度 一般情况下算法中基本操作重复执行的次数是问题规模n的某个函数f(n)进而分析f(n)随n的变化情况并确定T(n)的数量级。这里用O来表示数量级给出算法的时间复杂度。 T(n)O(f(n)); 它表示随着问题规模的n的增大算法的执行时间的增长率和f(n)的增长率相同这称作算法的渐进时间复杂度简称时间复杂度。而我们一般讨论的是最坏时间复杂度这样做的原因是最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界分析最坏的情况以估算算法指向时间的一个上界。 时间复杂度的分析方法
1、时间复杂度就是函数中基本操作所执行的次数
2、一般默认的是最坏时间复杂度即分析最坏情况下所能执行的次数
3、忽略掉常数项
4、关注运行时间的增长趋势关注函数式中增长最快的表达式忽略系数
5、计算时间复杂度是估算随着n的增长函数执行次数的增长趋势
6、递归算法的时间复杂度为递归总次数 * 每次递归中基本操作所执行的次数 常用的时间复杂度有以下七种算法时间复杂度依次增加O(1)常数型、O(log2 n)对数型、O(n)线性型、O(nlog2n)二维型、O(n^2)平方型、O(n^3)立方型、O(2^n)指数型. 空间复杂度 算法的空间复杂度并不是计算实际占用的空间而是计算整个算法的辅助空间单元的个数与问题的规模没有关系。算法的空间复杂度S(n)定义为该算法所耗费空间的数量级。 S(n)O(f(n)) 若算法执行时所需要的辅助空间相对于输入数据量n而言是一个常数则称这个算法的辅助空间为O(1); 递归算法的空间复杂度递归深度N*每次递归所要的辅助空间 如果每次递归所需的辅助空间是常数则递归的空间复杂度是 O(N).
例
1、求二分法的时间复杂度和空间复杂度。
非递归
templatetypename T
T* BinarySearch(T* array,int number,const T data)
{assert(number0);int left 0;int right number-1;while (right left){int mid (leftright) ((left^right)1);if (array[mid] data){right mid - 1;}else if (array[mid] data){left mid 1;}else{return (array mid);}}return NULL;
}分析 循环的基本次数是log2 N所以:
时间复杂度是O(log2 N);
由于辅助空间是常数级别的所以
空间复杂度是O(1); 递归
templatetypename T
T* BinarySearch(T* left,T* right,const T data)
{assert(left);assert(right);if (right left){T* mid left(right-left)/2;if (*mid data)return mid;elsereturn *mid data ? BinarySearch(left, mid - 1, data) : BinarySearch(mid 1, right, data);}else{return NULL;}
}递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的
时间复杂度:O(log2 N)
空间复杂度O(log2N ) 2、斐波那契数列的时间和空间复杂度
//递归情况下的斐波那契数列
long long Fib(int n)
{assert(n 0);return n2 ? n : Fib(n - 1) Fib(n-2);
}递归的时间复杂度是 递归次数*每次递归中执行基本操作的次数
所以时间复杂度是 O(2^N)
递归的空间复杂度是 递归的深度*每次递归所需的辅助空间的个数
所以空间复杂度是O(N) //求前n项中每一项的斐波那契数列的值
long long *Fib(int n)
{assert(n0);long long *array new long long[n 1];array[0] 0;if (n 0){array[1] 1;}for (int i 2; i n1; i){array[i] array[i - 1] array[i - 2];}return array;
}循环的基本操作次数是n-1,辅助空间是n1所以
时间复杂度O(n)
空间复杂度O(n)
//非递归
long long Fib(int n)
{assert(n 0);long long first0,second1;for (int i 2; i n; i){first first^second;second first^second;first first^second;second first second;}return second;
}循环的基本次数是n-1所用的辅助空间是常数级别的
时间复杂度O(n)
空间复杂度O(1)
