时间复杂度

Question

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

---

......两者都返回 \no 大多数。”那么数组的一半都没有多数 元素，并且组合数组不能有多数元素。所以， 调用返回\没有多数。”

b. 右侧是多数，左侧不是。唯一可能的多数 这个水平是右半部分占多数的值，因此， 只需比较组合数组中的每个元素并计算其数量 等于该值的元素。如果是多数元素则返回 该元素，否则返回\无多数。”

c. 与上面相同，但左侧返回多数，右侧返回 \no 大多数。”

d. 两个子调用都返回多数元素。计算相等的元素数量 给两位多数党候选人。如果其中一个是多数元素 放在组合数组中，然后返回它。否则，返回\无多数。” 顶层仅返回多数元素或不返回多数元素 以同样的方式存在。

因此，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< /code> 向量中不同元素的数量。

我这里是不是搞错了？或者 ...？

Answer 3

当您递归地执行此操作时，您将每个级别的数组分成两部分，对每一半进行调用，然后进行其中一个测试 a - 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;
}

Answer 4

这个人有很多关于递归关系的视频，以及可以用来解决它们的不同技术：
https://www.youtube.com/watch?v=TEzbkIggJfo&list=PLj68PAxAKGoyyBwi6qrfcsqE_4trSO1yL

基本上对于这个问题我会使用主定理：
https://youtu.be/i5kTZof1LRY

T(1) = 0 and T(n) = 2T(n/2) + 2n 
Master Theorem ==> AT(n/B) + 2n^D, so in this case A=2, B=3, D=1

所以根据主定理，这是 O(nlogn)

你也可以使用另一种方法来解决这个问题（如下），只是需要更多时间：
https://youtu.be/TEzbkIggJfo?list=PLj68PAxAKGoyyBwi6qrfcsqE_4trSO1yL

希望这对您有帮助！