какой из них будет быстрее?

Question

допустим, у меня есть массив размером 40. И искомый элемент находится в позиции 38. Имея простой цикл, это займет 38 шагов, верно?но, имея 2 цикла, работающих параллельно, и переменную "found", установленную в false, и изменяющуюся на true, когда элемент найден.

первый цикл начнется с индекса 0 второго цикла, начнется с индекса 40.

, так что в основном это займет всего 4 шага, верно?найти элемент.худший случай будет, если элемент находится в середине массива.право

Answer 1

Если вы говорите об алгоритмической сложности, это все еще линейный поиск.Тот факт, что вы ищете два элемента за одну итерацию, не меняет того факта, что алгоритм равен O (n).

С точки зрения фактической производительности этот алгоритм, вероятно, будет медленнее, чем линейный поиск с одним процессором.Поскольку для каждого элемента при поиске выполняется очень мало работы, алгоритм будет ограничен памятью, поэтому использование нескольких процессоров не принесет никакой пользы.Кроме того, поскольку вы выполняете поиск в двух местах, этот алгоритм не будет столь же эффективным с точки зрения кэширования.И затем, как указывает bwawok, при синхронизации будет много времени потеряно.

Answer 2

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

Если для этого потребуется 0 работ, то это будет в среднем на 50% быстрее, чем прямой алгоритм.*

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

С точки зрения алгоритма, я не думаю, чтокак ты хочешь пойтиДаже 2 потока все еще будут O (n) во время выполнения.Вы хотели бы отсортировать данные (n log n), а затем выполнить двоичный поиск, чтобы получить данные.Особенно вы можете отсортировать его 1 раз и использовать для многих поисков ...

Answer 3

В среднем во время выполнения нет различий.

Возьмем, к примеру, если вы ищете элемент из 10.
Исходный алгоритм будет обрабатываться в следующем поискеorder:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Худший случай - последний элемент (с 10 шагами).

Второй алгоритм будет обрабатываться в следующем порядке поиска:

 1, 3, 5, 7, 9, 10, 8, 6, 4, 2

Наихудший случай в этом сценарии - пункт 6 (с 10 шагами).

В некоторых случаях алгоритм работает быстрее 1.
В некоторых случаях алгоритм 2 работает быстрее.

Оба занимают в одно и то же время в среднем - O (n).

---

В примечании к теме интересно сравнить это с порядком двоичного поиска (в отсортированном массиве).

4, 3, 2, 3, 1, 4, 3, 2, 4, 3

Выполнение не более 4 шагов.

Answer 4

Когда вы работаете параллельно , вы делите мощность своего процессора на две части +, создавая некоторые издержки . Если вы имеете в виду, что вы выполняете поиск на, скажем, многоядерном компьютере с вашим предложенным алгоритмом, тогда худший случай - 20 шагов. Вы не вносите никаких изменений в класс сложности. Так откуда взялись те 4 шага, о которых вы упоминали?