洛阳建站公司效果,wordpress注册用户验证,云南楚雄地图全图,网站关键词的写法目录 1.时间复杂度
2.时间复杂度计算例题
3.空间复杂度 1.时间复杂度 算法中的基本操作的执行次数#xff0c;为算法的时间复杂度。 如何表达 时间复杂度#xff1f; 大O的渐进表示法 实际中我们计算时间复杂度时#xff0c;我们其实并不一定要计算精确的执行次数#xf…目录 1.时间复杂度
2.时间复杂度计算例题
3.空间复杂度 1.时间复杂度 算法中的基本操作的执行次数为算法的时间复杂度。 如何表达 时间复杂度 大O的渐进表示法 实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要 大概执行次数那么这里我们 使用大 O 的渐进表示法。 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中只保留最高阶项。 3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶 举例 // 请计算一下 func1 基本操作执行了多少次 void func1 ( int N ){ int count 0 ; for ( int i 0 ; i N ; i ) { for ( int j 0 ; j N ; j ) { count ; } } for ( int k 0 ; k 2 * N ; k ) { count ; } int M 10 ; while (( M -- ) 0 ) { count ; } System . out . println ( count ); } 题解 Func1 执行的基本操作次数 F(N)N^22*N10; (1) 用常数1取代运行时间中的所有加法常数。 F(N)N^22*N1 2 在修改后的运行次数函数中只保留最高阶项。 F(N)N^2; O(N^2); 通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项简洁明了的表示出了执行次数。 另外有些算法的时间复杂度存在最好、平均和最坏情况 最坏情况任意输入规模的最大运行次数 ( 上界 ) 平均情况任意输入规模的期望运行次数 最好情况任意输入规模的最小运行次数 ( 下界 ) 在实际中一般情况关注的是算法的最坏运行情况如数组中搜索数据时间复杂度为 O(N) O(N)中N表示问题的规模 2.时间复杂度计算例题 例题1 // 计算 func2 的时间复杂度 void func2 ( int N , int M ) { int count 0 ; for ( int k 0 ; k M ; k ) { count ; } for ( int k 0 ; k N ; k ) { count ; } System . out . println ( count ); } 答案及分析 基本操作执行了MN次有两个未知数M和N时间复杂度为 O(NM) 例题2 // 计算 func3 的时间复杂度 void func3 int N ) { int count 0 ; for ( int k 0 ; k 100 ; k ) { count ; } System . out . println ( count ); } 答案及分析 基本操作执行了100次通过推导大O阶方法时间复杂度为 O(1) 例题3 // 计算 bubbleSort 的时间复杂度 void bubbleSort ( int [] array ) { for ( int end array . length ; end 0 ; end -- ) { boolean sorted true ; for ( int i 1 ; i end ; i ) { if ( array [ i - 1 ] array [ i ]) { Swap ( array , i - 1 , i ); sorted false ; } } if ( sorted true ) { break ; } } } 答案及分析
O(N)中N表示问题的规模 F(N)N*(N-1)N^2-N; 通过推导大 O 阶方法 时间复杂度一般看最坏时间 复杂度为 O(N^2) 例题4 // 计算 binarySearch 的时间复杂度 int binarySearch ( int [] array , int value ) { int begin 0 ; int end array . length - 1 ; while ( begin end ) { int mid begin (( end - begin ) / 2 ); if ( array [ mid ] value ) begin mid 1 ; else if ( array [ mid ] value ) end mid - 1 ; else return mid ; } return - 1 ; } 答案及分析
方法1
对于不能直接看出的并较复杂的问题可以采用数学归纳法 答案 方法2 N/(2^x) 1x为循环的执行次数
x的解 例题 5 // 计算阶乘递归 factorial 的时间复杂度 long factorial ( int N ) { return N 2 ? N : factorial ( N - 1 ) * N ; } 对于不能直接看出的并较复杂的问题可以采用数学归纳法但对于递归我们有专门总结的方法。
FN递归的次数*每次递归代码的执行次数 答案及分析 通过计算分析发现基本操作递归了 N次 每次递归代码的执行次数为1 时间复杂度为O(N) 例题6 // 计算斐波那契递归 fifibonacci 的时间复杂度 int fifibonacci ( int N ) { return N 2 ? N : fifibonacci ( N - 1 ) fifibonacci ( N - 2 ); } 答案及分析
对于不能直接看出的并较复杂的问题可以采用数学归纳法不展开
面对这种多递归入口的题可以使用补全法。
何为补全法
以F4为例
FN 124……2^(N-1) 2^N-1; O(2^N) 3.空间复杂度 空间复杂度是对一个算法在运行过程中 临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少 bytes 的空 间因为这个也没太大意义所以空间复杂度算的是变量的个数 空间复杂度计算规则基本跟时间复杂度类似 也 使用大 O 渐进表示法 。 无论什么类型只看开了多少的空间 例题1 // 计算 bubbleSort 的空间复杂度 void bubbleSort ( int [] array ) { for ( int end array . length ; end 0 ; end -- ) { boolean sorted true ; for ( int i 1 ; i end ; i ) { if ( array [ i - 1 ] array [ i ]) { Swap ( array , i - 1 , i ); sorted false ; } } if ( sorted true ) { break ; } } } 答案及分析 使用了常数个额外空间所以空间复杂度为 O(1)
例题2 // 计算 fifibonacci 的空间复杂度 int [] fifibonacci ( int n ) { long [] fifibArray new long [ n 1 ]; fifibArray [ 0 ] 0 ; fifibArray [ 1 ] 1 ; for ( int i 2 ; i n ; i ) { fifibArray [ i ] fifibArray [ i - 1 ] fifibArray [ i - 2 ]; } return fifibArray ; } 答案及分析 动态开辟了N个空间空间复杂度为 O(N) 例题3 // 计算阶乘递归 Factorial 的空间复杂度 long factorial ( int N ) { return N 2 ? N : factorial ( N - 1 ) * N ; } 答案及分析 递归调用了 N 次开辟了 N 个栈帧每个栈帧使用了常数个空间。空间复杂度为 O(N) 以上为我个人的小分享如有问题欢迎讨论
都看到这了不如关注一下给个免费的赞
