我可以找到循环的时间复杂度'for'但是当条件发生变化时，我就卡住了。有没有数学方法来计算时间复杂度？

Question

Q1)

int a = 0, i = N; 
while (i > 0) { 
a += i; 
i /= 2; 
} 

问题 2)

int i, j, k = 0; 
for (i = n / 2; i <= n; i++) { 
for (j = 2; j <= n; j = j * 2) { 
k = k + n / 2; 
} 
} 

Answer 1

如果你只是用数学来处理它，事情可能会变得非常复杂。 大多数时候，最好通过算法的逻辑

。问题 1)i从N到0的变化。每次循环运行时，i(最初是N)减半，这为您提供了对数时间复杂度。O(log N)

问题 2)外循环运行n/2次，因此O(N/2)，根据时间复杂度规则，您删除常量，因此O(N)。

每次运行内部循环时，您都会将j的值加倍，这意味着您将 j 和 n 之间的距离以 2 的乘法缩小，这是对数的，所以O(log N).

由于内部循环针对外部循环中的每个元素运行，因此总时间复杂度为O(N log N)。

请注意，我没有考虑k = k + n / 2和a += i，因为这些操作在恒定时间O(1)运行，这是最不占主导地位的时间复杂度，因此对计算没有影响。