算法复杂度评价标准与平均情况计算

文章目录1.时间复杂度1.1 什么是时间复杂度1.2 常见特殊的时间复杂度计算举例1.3 计算时间复杂度的平均情况2.空间复杂度2.1 什么是空间复杂度算法效率分析分为两种第一种是时间效率第二种是空间效率。时间效率被称为时间复杂度而空间效率被称为空间复杂度时间复杂度主要衡量的是一个算法的运行速度而空间复杂度主要衡量一个算法所需要的额外空间。1.时间复杂度1.1 什么是时间复杂度算法的时间复杂度是算法执行步骤数量随输入规模 n 增长的趋势在程序中常用大 O 渐进表示法来表示。而之所以用大 O 表示法的原因是当 n 足够大时低阶项和常数项影响可以忽略决定性能的是“最高阶项”1.2 常见特殊的时间复杂度计算举例【示例 1】//计算binarySearch二分查找法的时间复杂度intbinarySearch(int[]array,intvalue){intbegin0;intendarray.length-1;while(beginend){intmidbegin((end-begin)/2);if(array[mid]value)beginmid1;elseif(array[mid]value)endmid-1;elsereturnmid;}return-1;}最坏情况是一条直线一直被不断的分为 1/2最终分成只剩一个其推导过程如下第一次n/2^1第二次n/2^2第三次n/2^3…第x 次n/2^x - n/2^x 1 - x log2N最终时间复杂度为 O(log2N)【示例 2】//计算阶乘递归factoria的时间复杂度longfactorial(intN){returnN2?N:factorial(N-1)*N;}计算公式递归的时间复杂度 递归的次数 * 每次递归执行的次数该样例计算即当 N 1,时则不再递归因此递归次数即为 N - 1而每次递归执行的语句为三目运算符语句其执行次数可视为 1因此为 O(N)【示例 3】//计算斐波那契递归fibnacci的时间复杂度intfibnacci(intN){returnN2?fibnacci(N-1)fibnacci(N-2);}以上为粗略计算过程因此其递归次数就为等比数列求和即可最终为O(2^n)1.3 计算时间复杂度的平均情况时间复杂度平均情况是在所有可能输入中按每种输入出现的概率加权后算法执行时间的数学期望。其公式表达情况为Ti(n)第 i 种情况的执行步数Pi该情况发生的概率∑ Pi1我们举一个范例比如线性查找 targetfor(inti0;in;i){if(arr[i]target)returni;}return-1;情况target 位置比较次数第 1 个01第 2 个12………第 n 个n-1n不存在—n常见合理假设target 在数组中等概率出现每个位置概率为 1/n1/n1/n或包含“不存在”的情况计算数学期望利用等差数列公式最终时间复杂度为 O(n)2.空间复杂度2.1 什么是空间复杂度空间复杂度是算法在执行过程中额外占用的内存空间随输入规模 n增长的趋势因为在比较算法的时候面对的是同一份输入因此不关心算法本身的空间而只为分析算法为了运行“多申请了多少空间”以后常遇到的复杂度有O(1) O(log2N) O(N) O(N*log2N) O(N2)其判断复杂度方法与时间复杂度类似参考时间复杂度即可以上是我关于Java的笔记分享也可以关注关注我的静态网站感谢你读到这里这也是我学习路上的一个小小记录。希望以后回头看时能看到自己的成长~