C++ 数据结构 时间复杂度
for（int p = 0;p<n*n ;p++ ）
for (int q = 0;q<p ;q++ )
S1；
其中，S1的执行时间为O（1），则整个程序的时间复杂度为多少？若将p<n*n 改为p<n*n*n 呢？若将q<p改为q<p*p 呢？
第1个回答 2014-06-30
for (int p = 0; p < n*n; p++)
for (int q = 0; q < p; q++)
S1; // 执行 (n*n) * (n*n-1) / 2 次, 所以是 O(n^4)
for (int q = 0; q < p*p; q++)
S1; // 具体次数不太好判断, 不过应该是O(n^9)本回答被提问者采纳
for (int q = 0; q < p; q++)
S1; // 执行 (n*n) * (n*n-1) / 2 次, 所以是 O(n^4)
for (int p = 0; p < n*n*n; p++)
for (int q = 0; q < p*p; q++)
S1; // 具体次数不太好判断, 不过应该是O(n^9)本回答被提问者采纳
第2个回答 2014-06-29
(n/2)*(n) = O(n^2)
满意请采纳。追问
满意请采纳。追问
请问为什么呢？可是答案是O（n^4）...
第3个回答 2020-03-06
相似回答
