算法的大O分析？

Question

这似乎是一种基于Mergesort的搜索算法。它将用于排序的数字数组。大O复杂度仍然是O(n log )吗？

public static boolean fastSearch(int[] data, int min, int max, int target)
{
     int N = data.length;
     boolean found = false;
     int midpoint = (min+max)/2; // determine the midpoint

     if (data[midpoint] == target) {
          found = true;
     } else {
          if (data[midpoint] > target) {
               if (min <= midpoint - 1) {
                    // Recursion on the left half of the array
                    found = fastSearch(data, min, midpoint-1, target);
               }
          } else {
               if (midpoint + 1 <= max) {
                    // Recursion on the right half of the array
                    found = fastSearch(data, midpoint+1, max, target);
               }
          }
     }
     return found;
}

这是我自己做的分析，我只想确认我是否正确：

每一次通过数据都会使子部分的大小加倍。在找到目标之前，需要反复加倍。它采用log(n)倍，数据的每一次传递都与项的数量成正比。因此，它是O(n log )。

Answer 1

在我看来，这是一个普通的二进制搜索算法，它已知具有O(log n)复杂性(除了返回值是否被找到，而不是它的位置)。基本上，最多只能“访问”数组条目的log n：

• 你先去看看中间的检查点，看看是不是你要找的那个，
• 如果没有，则将搜索限制为“较低”或“上”搜索数组的一部分，
• 所以你把表切成两半，然后只选择其中的一个部分，那么就只剩下一个元素了(最坏的情况--寻找的元素会在前面找到)，
• 你能做到多少次？n/2/2/2/2/.../2 = 1 -- /2的数量将是log n。

这不是严格的分析。可能会有一些不一致的错误，并且没有边界条件检查，但最终的结果肯定是O(log n)。

当然，我们必须假设data数组是排序的，n = max - min (和min < max)。否则那就是垃圾。

顺便说一句：f(n) = O(log n)意味着log n (从某种意义上说)是f(n)的上限(可能有一些正的常数因子)。f(n) = O(n log n)对n log n来说意味着同样的意思。所以是的，如果它受log n的限制，它肯定是受到n log n的限制(因为f(n) <= c1(log n) <= c2(n log n)对于所有的n个格林来说都是N的)，但这不是你想要的答案。