婚纱摄影网站模板,聊城开发网站建设,网站制作公司怎么收费,做网站建设一年能赚多少钱本章开始将进入数据结构的知识#xff0c;时间复杂度主要衡量的是一个算法的运行速度#xff0c;而空间复杂度主要衡量一个算法所需要的额外空间#xff0c;。 时间复杂度
算法中执行的次数决定了时间复杂度。
在计算执行次数时#xff0c;只需要计算大概的次数#xff… 本章开始将进入数据结构的知识时间复杂度主要衡量的是一个算法的运行速度而空间复杂度主要衡量一个算法所需要的额外空间。 时间复杂度
算法中执行的次数决定了时间复杂度。
在计算执行次数时只需要计算大概的次数即称为大O的渐进表示法以下是大O的渐进表示法计算执行次数时要注意的点
用常数1取代运行时间中所有加法常数例5 -》O(1)运行次数是一个函数时只保留最高阶项例n^22n1 -》 O(n^2)如果最高阶项存在且不是1就去除项的常数例2n -》O(n)
举几个例子更能了解时间复杂度
第一个例子 public static void func1(int n) {int count 0;for(int i 0; i 2*n; i) {count;}int m 10;while(m--0) {count;}System.out.println(count);}
上面这个例子的时间复杂度是O(n)为什么呢我现在就来说说 首先执行第一个循环for循环它的时间复杂度是2n然后就是进入第二个循环whlie循环它的复杂度是10然后这个程序就走完了总的复杂度是2n10。那为什么是n呢 就是因为大O的渐进表示法常数次数为1所以就是2n1但是1与2n相比没有什么区别那就是2n表示法中表明系数可去除所以综合下来就为n啦
第二个例子冒泡排序法 public static void bubbleSort(int[] array) {for(int i 0; i array.length; i) {for(int j 0; j array.length - 1; j) {if(array[j] array[j1]) {int temp array[j];array[j] array[j1];array[j1] temp;}}}} 在冒泡排序中有最好的情况也有最坏的情况最好是这个排序以及符合排序那只需要走一遍就可以即复杂度是O(N)最坏情况就是内外层循环都要执行以次那就是n*(n-1)次根据大O渐进表示法复杂度为O(N^2)。
第三个例子二分查找 public static int binarySearch(int[]array, int search) {int begin 0;int end array.length;while(begin end) {int mid begin (end -begin)/2;if (array[mid] search)begin mid 1;else if (array[mid] search)end mid - 1;else return mid;}return -1;}
二分查找的时间复杂度是O(log N)怎么计算的呢 假设该数组有N个元素第一次查找元素个数减去一半N/2第二次又减去一半N/2^2第k次时就只剩一个元素了那么就有N/2^k 1就得到log N2不写默认为2。
第四个例子阶乘递归 public long factorial(int N) {return N 2 ? N : factorial(N - 1) * N;} 递归的复杂度 递归的次数 * 每次递归执行的次数大概意思就是递归一次套一次套了多少次那就是递归得次数套一次中里面执行的次数就是每次地柜执行的次数。所以上面例子的复杂度是N*1次即O(2^N)。 斐波那契数列的复杂度是O(2^N)它是一个一分二二分四四分八等等将其累加起来就是2^N次。
常见的复杂度O(1) O (log N) O(N * log N) O (N^2)
空间复杂度 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。开辟了几个空间复杂度就是几为常数时复杂度是O(1)。
例如冒泡排序它创建了3个变量i j , temp所以复杂度是O(1)阶乘递归它每次调用一次方法也需要开辟一次空间所以它的空间复杂度是O(N)
