Сложность времени

Question

Проблема в нахождении большинства элементов в массиве.Я понимаю, как работает этот алгоритм, но я не знаю, почему он имеет O (nlogn) как сложность времени .....

---

a.Оба возвращают \ нет большинства. "Тогда ни половина массива не имеет элемента большинства, а объединенный массив не может иметь элемента большинства. Поэтому вызов возвращает \ нет большинства."

b.Правая сторона - большинство, а левая - нет.Единственное возможное большинство для этого уровня - это значение, составляющее большинство в правой половине, поэтому просто сравните каждый элемент в объединенном массиве и посчитайте количество элементов, равное этому значению.Если это элемент большинства, тогда вернуть этот элемент, в противном случае вернуть \ no большинству. "

c. То же, что и выше, но с левым возвращением большинства, а правым с возвращением \ без большинства."

д.Оба подзвона возвращают мажоритарный элемент.Подсчитайте количество элементов, равное обоим кандидатам на мажоритарный элемент.Если любой из них является элементом большинства в объединенном массиве, верните его.В противном случае, верните \ no большинству. "Верхний уровень просто возвращает либо мажоритарный элемент, либо что мажоритарный элемент не существует таким же образом.

Следовательно, 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.

Итак, мы получили log (n) итераций с O (n) операциями: nlog (n)

Answer 2

У этого парня много видеороликов о рекуррентных отношениях и различных методах, которые вы можете использовать для их решения: 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

Надеюсь, это поможет вам!

Answer 3

Когда вы делаете это рекурсивно, вы разбиваете массив на два для каждого уровня, делаете вызов для каждой половины, а затем выполняете один из тестов a - d.Тест a не требует зацикливания, другие тесты требуют зацикливания всего массива.В среднем вы будете проходить через (0 + 1 + 1 + 1) / 4 = 3/4 массива для каждого уровня в рекурсии.

Количество уровней в рекурсии основано на размеремассив.Когда вы разделите массив пополам на каждом уровне, количество уровней будет log2 (n).

Итак, общая работа равна (n * 3/4) * log2 (n).Поскольку константы не имеют отношения к сложности времени, и все логарифмы одинаковы, сложность равна O (n * log n).

Edit:

Если кто-то интересуется алгоритмом, вотреализация 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

Я не уверен, что понимаю, но не могли бы вы просто создать хеш-карту, пройтись по массиву, увеличивая hash[value] на каждом шаге, затем отсортировать хеш-карту (сложность времени xlogx) и сравнить верхнюю частьдва элемента?Это будет стоить вам O(n) + O(mlogm) + 2 = O(n + mlogm), с n размером массива и m количеством различных элементов в векторе.

Я ошибаюсь здесь?Или ...?