如何计算生产中现有代码的时间复杂度

Question

为了理解使用操作计数和步骤计数技术的程序的时间复杂度，我已经通过几个示例进行了了解，但是这些示例很小而且很直接。然而在现实世界的编程中，如果有人给你生产或实时代码来找到它的最坏情况时间复杂度。如何开始分析它？

有什么分析程序的技巧或经验法则吗？假设我有一个如下所示的函数，它具有 if 和 for 条件。对于 n 的某些值，它会很深，但对于某些值，它不会。所以最大操作数是最坏的情况，最小操作数是最好的情况。如果我们有这种条件语句，我们怎么知道什么时候会发生最大操作呢？（其他功能可以更深入的条件而不是循环）

int l = 0;
while (l <= n){
  int m = l + (n-l)/2; 
     
  if (arr[m] == x) return;   
  if (arr[m] < x) l = m + 1;  
  else n = m - 1;  
}

看上面的代码，怎么计算出最坏情况和最好情况？执行上述程序的步骤计数并通过代入 n = 1 到 20 并获得一些值然后尝试推导函数？我想知道当人们有这种分支语句时，他们如何分析现有代码的时间复杂度。

Step by Step analysis or Set of statements to follow 解决上述问题会很有帮助。

Answer 1

因为每次 n 的一半被添加到 m 并且循环将通过增加一个单位 l 或改变 [=11= 的值来继续]给m-1下面的场景可以给出最大的操作：

In each iteration, the `else` part is happened and set `n` to `m-1`.

让我们看看这个案例发生了什么。由于每次 n 被 2 分红，并且 l 保持 0，在 O(log(n)) 迭代之后，l == n.

因此循环的时间复杂度为O(log(n)).

请注意，其他情况可以 l 更快地增加到 n。例如，如果l = m + 1表示l = (n-1)/2，在下一次迭代中，m将增加到n-1。因此，只需 2 次迭代，我们就必须到达循环的末尾。

How to calculate time complexity of existing code in production