Обходной элемент от 1 до n меньше, чем O (n)

Question

Как пройти от 1 до n менее чем за O (n).

например.

arr[] = {1,2,3,4,5,6,7,8,9}

Мы хотим напечатать:

1 2 3 4 5 6 7 8 9 less than O(n) or O(n/2)

Answer 1

Это невозможно по той простой причине, что для печати в общей сложности k символов требуется, чтобы вы выполнили не менее k операций, и при выводе значений от 1 до n включительно должно быть напечатано не менее n символов.

(На самом деле существует Θ (n log n) символов, так как количество символов, необходимое для записи числа n в некоторой фиксированной базе, равно Θ (log n)).

Answer 2

Поскольку для печати элементов n вам нужно будет хотя бы один раз прикоснуться к каждому элементу, @IlyaBursov правильно упомянул в комментарии, что это невозможно.

---

Важный отказ от ответственности:

Мне глупо добавлять что-либо еще в ответ на этот вопрос. Пункты ниже относятся к другому топи c. Они демонстрируют другие способы думать о решении проблемы, а не пытаться превратить невозможность в возможность.

---

При этом можно сказать, что вы можете разделить работу между несколькими потоками, особенно если не важно печатать их по порядку и обрабатывать задачу параллельно.

Это сократит ваше время выполнения с O (n) до O (n / k) где k - количество запущенных вами параллельных процессов, при условии:

1. У вас по крайней мере k свободных ядер; и
2. n> k.

Тем не менее, общая работа, которую вы сделали в этом случае, по-прежнему:

= O (n / k) работа на поток * k потоков

= O ((n / k) * k)

= O (n)

---

Предостережение в отношении многопоточности:

Если вы собираетесь запускать потоки, когда получаете задачу, это добавит дополнительное время выполнения. Поэтому вам нужно, чтобы потоки работали в пуле, а затем назначить им часть массива, которую они должны обработать.

Если вы повторите этот процесс достаточно много раз, то затраты на создание k потоки в первый раз будут амортизироваться и будут полностью смещены.