读书人

关于数据结构的running time有关问题

发布时间: 2013-01-11 11:57:35 作者: rapoo

关于数据结构的running time问题
for(int i=0;i<n;i++)
for(int j=0;j<i^3;j++)
if(j%i^2==0)
for(int k=0;k<n^2;k++)
l++;

这类题目怎么看,i<n记O(n),但是 j<i^3也要记O(n^3)吗 数据结构
[解决办法]
一个一个算
i比较了n次
j比较了1^3+2^3+...+n^3=O(n^4)次
后面%i^2和j的比较次数一样
判断里面的运行次数和j比就少多了,对总体复杂度不产生影响

因此总体复杂度应该是O(n^4)

读书人网 >C++

热点推荐