Найти верхние значения log (n) или top sqt (n) в массиве целых чисел

Question

Понимаете ли вы, что означает этот вопрос

Найдите лучшие значения log (n) или top sqt (n) в массиве целых чисел менее чем за линейное время.

Если вы неt, вот вопрос http://www.careercup.com/question?id=9337669.

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

Спасибо за ваше время.

Answer 1

Для несортированного массива сложность линейна, но можно улучшить производительность, наблюдая, что log (n) и sqrt (n) являются монотонной функцией роста, следовательно, max (log (n), ...) также log (max (n, ...)) и то же самое для sqrt.

Так что просто найдите max (n) (линейно) и вычислите log и sqrt.

Answer 2

Предполагая, что массив не отсортирован, эта проблема равна Omega(n), так как вам нужно прочитать все элементы [поиск max - это Omega(n) проблема в несортированном массиве, и эта проблема не легче, чем поиск max].Таким образом, для него нет сублинейного решения.

Существует O(n) [линейное] решение, использующее алгоритм выбора

1. find the log(n) biggest element. //or sqrt(n) biggest element...
2. scan the array and return all elements bigger/equal it.

(*) Этот псевдокодневерно, если массив содержит дубликаты, но обрезать дубликаты на втором шаге довольно просто.