时间复杂度

Question

问题是在数组中找到大多数元素。我理解这个算法是如何工作的，但我不知道为什么O(nlogn)是一个时间复杂度。

“那么数组的一半都没有多数元素，组合的数组不能有多数元素。因此，调用返回零多数。”

右边是多数，左边不是。这个级别唯一可能的多数是在右半部分形成多数的值，因此，只需比较组合数组中的每个元素，并计算与此值相等的元素数。如果它是一个多数元素，那么返回该元素，否则返回\没有多数。“

c.与上述相同，但左侧为多数，右侧为多数\无多数。“

两个子调用都返回一个多数元素。计算与多数元素的两个候选人相等的元素数。如果两者都是组合数组中的多数元素，则返回它。否则，返回\没有多数。“顶级只返回多数元素或不存在相同方式的多数元素。

因此，T(1) =0，T(n) = 2T(n/2) + 2n = O(nlogn)

我认为,

每一次递归，它将多数元素与整数组进行比较，整个数组取2n。

T(n) = 2T(n/2) + 2n = 2(2T(n/4) + 2n) + 
      2n = ..... = 2^kT(n/2^k) + 2n + 4n + 8n........ 2^kn = O(n^2)

Answer 1

T(n) = 2T(n/2) + 2n

问题是，n到1需要多少次迭代。

在每次迭代中，我们除以2，得到一个级数:n，n/2，n/4，n/8 . n/(n^k)

因此，让我们找到k，它将使我们达到1(最后一次迭代)：

n/(2^k)=1 .n=2^k . k=log(n)

所以我们得到了log(n)迭代。

现在，在每一次迭代中，我们都执行2n运算(较少，因为我们每次将n除以2)，但在有价值的情况下，假设为2n。

因此，总的来说，我们使用O(n)操作进行了log(n)迭代：nlog(n)

Answer 2

我不确定我是否理解，但您不能创建一个哈希映射，遍历数组，在每一步递增hash[value]，然后排序哈希映射(xlogx时间复杂度)并比较前两个元素吗？这将花费您的O(n) + O(mlogm) + 2 = O(n + mlogm)，使用n表示数组的大小，并使用m表示向量中不同元素的数量。

我搞错了吗？还是.？

Answer 3

当您递归地执行此操作时，您将每个级别的数组分成两部分，每半个调用一次，然后使其中一个测试为- d。测试a不需要循环，其他测试则需要遍历整个数组。平均而言，您将遍历递归中每个级别的数组的(0 +1+1+ 1) /4=3/4。

递归中的级别数基于数组的大小。当您将数组拆分为每个级别的一半时，级别数将为log2(n)。

因此，总功是(n * 3/4) * log2(n)。由于常数与时间复杂度无关，而且所有对数都是相同的，所以复杂度是O(n * log n)。

编辑：

如果有人想知道算法，下面是一个C#实现。:)

private int? FindMajority(int[] arr, int start, int len) {
  if (len == 1) return arr[start];
  int len1 = len / 2, len2 = len - len1;
  int? m1 = FindMajority(arr, start, len1);
  int? m2 = FindMajority(arr, start + len1, len2);
  int cnt1 = m1.HasValue ? arr.Skip(start).Take(len).Count(n => n == m1.Value) : 0;
  if (cnt1 * 2 >= len) return m1;
  int cnt2 = m2.HasValue ? arr.Skip(start).Take(len).Count(n => n == m2.Value) : 0;
  if (cnt2 * 2 >= len) return m2;
  return null;
}