второе по величине число в массиве не более n + log (n) -2 сравнений

Question

Когда я вижу эту проблему, я думаю, что могу использовать разделяй и властвуй, чтобы решить Диаграмма алгоритма

секунда - мой код программный код извините, я не могу написатьэто здесь, потому что я написал это во встроенном компиляторе, и файл не сохранил

код работает хорошо, но когда я вычисляю сравнение n, оно было больше, чем n + log (n) -2

мой вопрос (проблема) заключается в том, что я не могу решить проблему, основываясь на определенном времени выполнения или конкретном сравнении. Я решаю проблему, а затем вычисляю сравнение

Я говорю в общем, не только для этой проблемы

Как я могу спроектировать (подумать) алгоритм, основанный на времени выполнения, есть ли шаги, которым нужно следовать или что

Answer 1

Запустить отборочный турнир (n - 1 сравнение).Второй по величине должен быть среди тех, кто проиграл чемпиону, и их log n.Найдите наибольшего из кандидатов в log(n) - 1 сравнениях.

Самое сложное - разработать эффективную структуру данных, чтобы иметь под рукой списки побежденных противников.Это очень нетривиально.Например, посмотрите на решение Алекса Степанова .

PS: Я настоятельно рекомендую весь курс .