讲解一下如何算时间复杂度

1.（时间复杂度计算）
有以下程序，计算时间复杂度。
num =0;
for ( i =1; i <= n ; i =¡2)
for ( k =1; k <= n ; k = k +2)
{ num ++;
}
2.（时间复杂度计算）
num =0;
for ( i =1; i <= n ; i =¡2)
for ( k =1; k <= i ; k = k +2)
{ num ++;
}

1

2

1.要计算时间复杂度，先计算循环次数
第一个循环，外层i每次加倍，那么循环次数就是log n次，内层每次+2，循环次数是n/2次
总的循环次数要相乘，就是n/2 x log n
第二个循环，外层还是logn次，内层条件变了不是n是i，那么围成的不是一个正方形是三角形，所以是n/4次
最终相乘之后得到n/4 x log n
2.时间复杂度是一个关于n的表达式，只包含n自身及各种对数、指数计算，不包含系数和常数项，你可以理解为先对它整体微分再积分
那么去掉所有的系数和常数项之后，第一个循环的复杂度是O(nlogn)，第二个循环的复杂度也是O(nlogn)