algorithm - 该算法的复杂度函数

Question

我试图找到该算法的最坏情况复杂度函数，将比较语句视为最相关的操作。那时候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;
}

Answer 1

定性理解

---

好吧，让我们尝试查看循环不变量，以确定该函数将运行多长时间。

我们可以看到函数会一直执行代码直到这个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)所以我们可以得出结论，您的算法在 O(lgn) 中运行