Самый быстрый способ найти минимальное значение в каждой колонке

Question

У меня есть log n строк, и каждая строка содержит номера n.

Я хочу найти минимальное значение в каждой позиции среди всех строк:

[1, 2, 3, 4, 5, 6, 7, 8] 
[2, 3, 4, 1, 2, 3, 4, 5] 
[3, 6, 7, 8, 3, 4, 1, 2] 
[9, 7, 2, 3, 2, 1, 3, 1] 

должен привести массив вида:

[1, 2, 2, 1, 2, 1, 1, 1] 

Я бы легко сделать скотину метод силы в O(nlogn) время

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

Но я не вижу способа удалить n. То, как я это вижу, мне нужно посмотреть каждую позицию по крайней мере в одной из строк хотя бы один раз.

Есть ли способ уменьшить сложность?

Answer 1

Если массив размера X не отсортирован или не структурирован каким-либо известным специальным способом, тогда стоимость нахождения элемента y в нем должна быть равна X, поскольку вы не можете пропустить любой элемент в X (пропущенный может быть решение).

Порядок поиска не имеет значения. Если вы разделите его и разделите и победите и т. Д., Тем не менее элемент y может быть последним, который вы посещаете.

Поэтому, если у вас есть массив размером n*logn, то минимально возможная сложность - Omega(n* log n).