算法——算法的时间与空间复杂度
16lz
2021-02-17
算法的时间与空间复杂度
事后分析法
缺点:不同的数据规模,不同的机器下算法运行的时间不同,无法做到计算运行时间
事前分析法
大O时间复杂度
渐进时间复杂度 随着n的增长,程序运行时间跟随n变化的趋势
几个原则
去掉常数项
2(n^2) =n^2
一段代码取时间复杂度最高的
test(n) { //时间复杂度n^3 for(int i = 0; i < n ; i++){ for(int i = 0; i < n ; i++){ for(int i = 0; i < n ; i++){ print(n); } } } //时间复杂度n^2 for(int i = 0; i < n ; i++){ for(int i = 0; i < n ; i++){ print(n); } } //时间复杂度n for(int i = 0; i < n ; i++){ print(n); }}
这段代码的时间复杂度为n^3+n^2+n
当n足够大时,n^2和n与n^3相比太小,可以忽略不计
常见复杂度
o(1)
i = i + 1;
o(n)
test(n){ for(int i = 0 ;i < n;i++){ print(i); }}
o(n^2)
test(n){ for(int i = 0 ;i < n;i++){ print(i); for(int j = 0 ;j < n;j++){ print(i); } }}
o(log2n)
PS:如果ax =N(a>0,且a≠1),那么数x叫做以a为底N的对数,记作x=logaN,读作以a为底N的,其中a叫做对数的底数,N叫做真数。
test(n) { int i = 1; while (i <= n) { i = 2 * i; }}
随着循环次数的增加,i的值变化如下
根据对数函数的公式 2的i次方等于n,i等于log2n
最好情况时间复杂度
数据比较有序的情况的时间复杂度
最坏情况时间复杂度
数据完全无序
空间复杂度
与n无关的代码空间复杂度可以忽略
空间复杂度O(n)
test(n) { //在内存中开辟了一个长度为n的数组 List array = List(n); print(array.length);}
©著作权归作者所有:来自51CTO博客作者wx602cc484254ab的原创作品,如需转载,请注明出处,否则将追究法律责任
更多相关文章
- 听说优秀的程序员20%的时间都在写UT?
- PHP指定时间戳加上1天,1周,1月
- SpringCloud 服务的平滑上下线
- 从博客时间轴总结这一年
- 用httping测试WEB页面响应时间
- centos7下配置ntp客户端同步时间服务(包括解遇到ntp无法开机启动
- 花时间打磨自己才是最有意思的人类活动
- 从来不相信快速会成就一件事,我只相信笨功夫
- 人生做减法,生活才会有更多的自由和平安