该算法的复杂度函数

Complexity function of this algorithm

我试图找到该算法的最坏情况复杂度函数，将比较语句视为最相关的操作。那时候if和else if都一直在循环下执行，所以函数就是2*循环执行次数。

由于每次复杂度可能为 O(log n) 时变量 i 都会增加一个更大的数字，但我如何找到准确的执行次数？谢谢

  int find ( int a[], int n, int x ) {    
  int i = 0, mid;
  while ( i < n ) {
     mid = ( n + i ) / 2;
     if ( a[mid] < x )
        n = mid;
     else if ( a[mid] > x )
        i = mid + 1;
     else return mid;
     }
return 0;
}

定性理解

好吧，让我们试着看一下循环不变量来弄清楚这个函数要运行。

多长时间

我们可以看到函数会继续执行代码，直到满足这个while(i < n){ ... }条件。

我们还要注意，在这个 while 循环中，i 或 n 总是 变异为 mid:

的一些变体 
if ( a[mid] < x )        # Condition 1:
    n = mid;             #   we set n to mid
else if ( a[mid] > x )   # Condition 2:
    i = mid + 1;         #   we set i to mid+1
else return mid;         # Condition 3: we exit loop (let's not worry about this)

所以现在让我们关注 mid，因为我们的 while 条件似乎总是根据这个值被削减（因为 while 条件取决于 i和n，其中一个会在每次循环迭代后设置为mid的值）：

mid = ( n + i ) / 2;     # mid = average of n and i

在查看函数的这些部分后，我们可以有效地了解这里发生了什么：

The function will execute code while i < n, and after each loop iteration the value of i or n is set to the average value, effectively cutting down the space between i and n by half each time the loop iterates.

这个算法被称为 binary search，它背后的想法是我们每次在循环中迭代时都将数组边界减半。

所以你可以把它想象成 我们一直把 n 切成两半，直到我们不能再切成两半为止。


定量分析

从数学上看，我们每次迭代都将 n 除以 2，直到 i 和 n 彼此相等（或n < i).

那么让我们考虑一下 我们可以将 n 除以 2 多少次直到它等于 1？在这种情况下，我们希望 n 等于 1，因为那时我们无法进一步拆分列表。

所以我们剩下一个等式，其中 x 是我们需要执行 while 循环的时间量：

n/2^x = 1
n = 2^x
lg(n) = lg(2^x)
lg(n) = x lg(2)
lg(n) = x

如您所见，x = lg(n) 因此我们可以得出结论，您的算法 运行s 在 O(lgn)

中