Приведенное выше обсуждение предполагает, что все элементы в куче являются уникальными (или что «второй наименьший» означает «меньше или равен наименьшему»). Если в куче могут быть повторяющиеся элементы и вам нужно второе наименьшее уникальное значение, то сложность равна O (n).
у базовый класс Comp 250, и этот вопрос мне дали. Никто не смог разобраться в этом вопросе. Возможные ответы приведены внизу. Получите минимальную кучу H, дайте жесткую оценку O () временной сложности метода find3Min, который находит, но не удаляет три наименьших ключа в H.
Предположим, что метод создает и возвращает список трех самых маленьких элементов. Чтобы ответить на этот вопрос, вам нужно подумать о том, как такой метод может быть реализован.
1- O (n log (n))
2- O (log (n))
3- O (3 log (n))
4- O (1)
на данный момент я склоняюсь к 4