Мы будем благодарны за любую помощь относительно того, как можно подойти к указанной ниже проблеме. Я также опубликовал некоторые мысли по проблеме.
Вы - ТА класса, в котором обучается n студентов. У вас есть их окончательные оценки (без сортировки), и вы должны присвоить им одну из доступных оценок G (A, B, C и т. Д.). Ограничения следующие (при условии, что n кратно G):
- Ровно (n / G) учеников получают каждую оценку (например, если n = 30 и G = {A, B, C}, то ровно 10 учеников получают A, 10 получают B и 10 получают C)
- Учащийся с более низким баллом не получает более высокую оценку, чем учащийся с более высоким баллом (однако они могут получить одинаковую оценку). Предполагая, что каждый учащийся получил разную оценку, выведите эффективный алгоритм и укажите его сложность в терминах n. и G. Любой алгоритм, который первым сортирует оценки, получит нулевой балл.
Мой ответ: Хорошо, в последней строке проблемы говорится, что я не годен, если я попытаюсь сначала отсортировать массив и разделить массив на G равных частей. Это займет O (n log n), если используется лучший алгоритм сортировки. Итак, я подумал о хитроумном решении. Я рассматриваю эту проблему как случай, когда быстрая сортировка может оказаться полезной, поскольку нам не нужно сортировать учащихся, принадлежащих к одному классу, у нас может быть k основных элементов, и все ключевые элементы расположены на одинаковом расстоянии. Но нам не выставляют оценки учеников, и нам также говорят, что у каждого ученика разные оценки.
Во-первых, я вычисляю максимальную и минимальную оценку, используя алгоритм MaxMin Divide and Conquer Algorithm, который займет время O (n). Используя Максимум и Минимум, мы можем приблизительно найти ключевые элементы для каждой оценки путем вычислений. (Макс-Мин) / k = самая низкая оценка, 2 * (Макс-Мин) / k = 2-я самая низкая оценка. и k-1 * (Макс-Мин) / k = высшая оценка.
Теперь, используя их в качестве основных элементов, мы можем выполнить только метод разделения для быстрой сортировки, который занимает n количество времени в первый раз, n- (Max-Min) / k во второй раз и так далее. Таким образом, временная сложность алгоритма будет O (n), поскольку задача min-max имеет сложность O (n), а Partition in Quick sort имеет сложность O (n).
Пожалуйста, поделитесь своими мыслями.
