关于数据结构的running time有关问题
关于数据结构的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)
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)