Я проснулся с заданием «Анализ алгоритма» и застрял в этом вопросе, я должен представить его завтра, и мне нужна помощь. Пожалуйста, ответьте, если вы можете решить это.
Учитывая массив A из n чисел, напишите эффективный алгоритм, чтобы найти наиболее часто
произошел элемент в этом массиве (режим этого массива). Также проанализируйте временную сложность вашего
алгоритм.
Поскольку это задание, я дам вам подсказку только о верхних границах сложности и аналогичной проблеме.
Эта проблема немного сложнее, чем Проблема отличимости элемента1. Проблема отличимости элементов известна как не может быть решена лучше, чем O(nlogn)
худший случай. Решения для отличимости элементов:
O(nlogn)
O(n)
средний случай и O(n^2)
худший случай и O(n)
дополнительное пространствоПодумайте об обоих подходах и подумайте, как вы можете изменить их, чтобы решить вашу проблему.
Кроме того, нижняя граница отличимости элементов говорит о том, что не будет лучшего алгоритма, чем O(nlogn)
худший случай.
(1) Проблема Различия Элементов: Все ли элементы в массиве различны? Или есть какой-то элемент, который также имеет дубликат самого себя?