数据结构与算法基础------计算时间复杂度

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法基础------计算时间复杂度，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1357字，纯文字阅读大概需要2分钟。

内容图文

算法效率从以下两个方面考虑：

1. 时间效率：指的是算法所耗费的时间
2. 空间效率：指的是算法执行过程中所耗费的存储空间

时间 效率和空间效率有时候是矛盾的。
在这里我们只讨论事前分析法，因为事后分析法也和计算机的软硬件等其他客观条件有关。
事前分析法
一个算法的运行时间大致等于计算机执行一种简单操作（如赋值，比较，移动等）所需的时间与算法中进行的简单操作的次数的乘积。
以矩阵为例：

for(i=1;i<=n;i++)		//n+1次
	for(j=1;j<=n;j++)	//n*(n+1)次
	{
		c[i][j]=0;		//n*n次
		for(k=0;k<=n;k++)	//n*n*(n+1)次
			c[i][j]=c[i][j]+a[i][k]*b[k][j];//n*n*n次
	}

那么上述算法所消耗的时间是该算法中每条语句的执行次数之和，则消耗的时间T(n)=2n³ +3n² +2n+1。
为了便于比较不同算法的时间效率，我们仅比较他们的数量级。

• 若某个辅助函数f(n)（即只包含最高数量级的函数），使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为时间复杂度。

---

分析算法时间复杂度的方法：

• 找出语句频度最大（即算法执行次数最多）的那条语句作为基本语句
• 计算基本语句的频度得到的问题规模n的某个函数f(n)
• 取其最高数量级的用符号O表示

时间复杂度是由嵌套最深层语句的频度决定的。
例：

void exam(float x[][],int m,int n)
{
	float sum[];
	for(int i=0;i<m;i++)
	{
		sum[i]=0.0;
		for(int j=0;j<n;j++)
			sum[i]+=x[i][j];//嵌套最深层
	}

例题：

i=1;	
while(i<=n)
	i=i*2;

设执行次数为x
2^x <=n
x<=log₂n
则执行次数最大为log₂n ，T(n)=O(log₂n )

• 点赞
• 收藏
• 分享
• • 文章举报

柳叶lhy 发布了14 篇原创文章 · 获赞 0 · 访问量 278 私信 关注

内容总结

以上是互联网集市为您收集整理的数据结构与算法基础------计算时间复杂度全部内容，希望文章能够帮你解决数据结构与算法基础------计算时间复杂度所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---