首页分享几个简单的时间复杂度计算问题

几个简单的时间复杂度计算问题

来源：花匠小妙招时间：2024-12-15 11:38

x=90; y=100; while(y>0)if(x>100){x=x-10;y--;}else x++; 12345

答：x=90,y=100，直接进入else语句x++，f(n)=1，所以时间复杂度T(n)=O(1).

for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0; 123

答：第一个for循环执行n次，第二个for循环执行m次，a[i][j]的f(n)= nm,所以时间复杂度T(n)=O(nm).

s=0;for i=0; i<n; i++)for(j=0; j<n; j++) s+=B[i][j]; sum=s; 12345

答：第一个for循环执行n次，第二个for循环执行n次，s+=B[i][j]的f(n)= n2,所以时间复杂度T(n)=O(n2).

i=1; while(i<=n)i=i*3; 123

答：i=1,3,9…，设循环次数是x，i=3x,循环条件是i<=n，即3x<=n，所以x<=log3n, 所以时间复杂度T(n)=O(log3n).

x=0; for(i=1; i<n; i++) for (j=1; j<=n-i; j++)x++; 1234

答：T(n)=1+2+3+…+(n-1)=n(n-1)/2，所以时间复杂度T(n)=O(n2).

x=n; //n>1 y=0; while(x>=(y+1)* (y+1)) y++; 1234

答：z次循环后，y的值为z，退出循环条件是n<(y+1)2即n<(z+1)2，z>√n–1，所以时间复杂度T(n)=O(√n).

相关文章：
《C#开发WindowsForm程序Load事件未注册》
《Visual Studio 2013如何显示代码行数》
《PCI DSS不合规的处理方法》
《PHP语言实现网站登录功能》
《PHP实现退出登录功能》
《LayUI数据表格查询与重载》
《PHP+MySQL+LayUI分页查询显示》

作者：戴翔
电子邮箱：daixiangcn@outlook.com
微信开发者主页：Null
简介：中国公民，CSDN博客专家，秦淮区疾控中心托管社会公益组织指南针工作室志愿者，创业公司研发中心负责人，在校大学生。第二届大学生微信小程序应用开发大赛全国三等奖项目第一作者，微信小程序《约车吗》、《庆云慈善会》、《锋云速检》项目总工程师。