为什么这段代码中的时间复杂度为O(n ^ 2)? [英] Why is the time complexity O(n^2) in this code?
本文介绍了为什么这段代码中的时间复杂度为O(n ^ 2)?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我只是不明白,为什么时间复杂度是O(n ^ 2)而不是O(n * logn)? 第二个循环每次递增2,所以它不是O(logn)吗?
I just didn't get it, why the time complexity is O(n^2) instead of O(n*logn)? The second loop is incrementing 2 each time so isn't it O(logn)?
void f3(int n){
int i,j,s=100;
int* ar = (int*)malloc(s*sizeof(int));
for(i=0; i<n; i++){
s=0;
for(j=0; j<n; j+=2){
s+=j;
printf("%d\n", s);
}
free(ar);
}
推荐答案
通过递增2而不是1,您正在执行以下N*N*(1/2)
.使用big(O)表示法时,您无需关心常数,因此它仍然是N * N.这是因为big(O)表示的是算法增长的复杂性.
By incrementing by two, rather than one, you're doing the following N*N*(1/2)
. With big(O) notation, you don't care about the constant, so it's still N*N. This is because big(O) notation reference the complexity of the growth of an algorithm.
这篇关于为什么这段代码中的时间复杂度为O(n ^ 2)?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文