算法的大O分析？

Question

它似乎是一种基于Mergesort的搜索算法.它用于排序的数字数组.Big-O复杂性仍然是O(n log n)吗？

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 n).

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)但这不是你正在寻找的答案.