衡量算法的性能-时空复杂度分析
算法
即存在输入输出,由有限步骤结束的程序.
因此,显而易见,算法并不是指一个单一的标准答案,而是一切能够完成要求的程序都可以称之为算法.但是算法之间根据性能的不同存在差异,评判这个差异的指标就是本篇分享的重点.
评判算法优劣的指标
1.时间复杂度
时间复杂度用O()表示,它的实质是算法的计算次数
这里先列举几个小例子
第一个例子
int n,ans=0;
cin>>n;
for(int i=0;i<n;i++){
ans++;
}
ans++;
ans++;
ans++;
cout<<ans;
这段程序比较好理解,在这里,for循环中进行了n次运算,而之后对ans又进行了3次运算,在这里我们的有效计算次数为n+3.
但是这里需要注意时间复杂度并不是n+3,因为我们在实际操作时,n是会取到无穷大的,在这里n就是无穷,对于无穷来说,3就可以忽略不计,因此这段程序的时间复杂度为O(n).
再看一下第二个例子
int n,ans=0;
cin>>n;
for(int i=0;i<n;i+=2){
ans++;
}
cout<<ans;
这次不过多解释,有效计算次数为n/2,但因为n是趋于无穷的,所以时间复杂度仍然为O(n).
第三个例子
int n,ans=0;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
ans++;
}
}
for(int i=1;i<=n;i++){
ans++;
}
cout<<ans;
这次的代码有两个循环,第二个是n,第一个则是作为一个嵌套循环,比较容易得出经过了n*n次循环
这次的有效计算次数为n2+n,由于n趋向无穷,对n2来说,n可以忽略不计,所以这次的时间复杂度为O(n2).
最后一个例子
int arr[101];
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>arr[i];
for(int i=n-1;i>0;i++){
for(int j=0;j<i;j++){
if(arr[j]>arr[j+1]){
swap(arr[j],arr[j+1]);
}
}
}
这是一个冒泡排序算法,这次的有效计算次数为1+2+3+...+n-1,由等差数列的求和公式知道为(n2+n)/2.经过前面的例子,想必都知道了时间复杂度就是不带系数最高次项,这里就是O(n2)
经过上面的例子大家应该对算法的时间复杂度有了比较清晰的认识,这里我再补充几点
1.有限计算次数即没有n加入的程序,规定时间复杂度为O(1).
2.常见的时间复杂度有:O(1),O(logn),O(n),O(n2),O(n3).
2.空间复杂度
事实上在实际情况下,空间复杂度没有时间复杂度受重视,在实际学习中,大多数情况下是超过了运行时间,而不是超过规定内存.但它同样需要我们了解.
时空复杂度也用O()表示,它的实质是额外产生的空间.
int arr[101];
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>arr[i];
int *arr=new int[n];
for(int i=n-1;i>0;i++){
for(int j=0;j<i;j++){
if(arr[j]>arr[j+1]){
swap(arr[j],arr[j+1]);
}
}
}
delete[]arr;
这里需要关注的是空间复杂度是额外产生的空间,因此初始的n个不计入空间复杂度,而之后的new出来的内存是空间复杂度,即为n,它的计算方法和时间复杂度一样,取不带系数的最高次项.
补充几点:
1.时间和空间往往是相对的.
2.常见的空间复杂度:O(1),O(n),O(logn*n)
3.稳定性
这里简单提一下,不过多赘述,后续会专门开一个新坑讲解一下.
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十