Временная сложность обхода массива

Ниже приведены два способа обойти любой массив:

  1. При использовании цикла for переменная будет проходить от начала до конца массива.
  2. Использование переменных цикла while 2 будет проходить в противоположном направлении и встречаться между ними.

Как будет меняться временная сложность, будет ли она уменьшена во втором случае или останется такой же?


traversal time-complexity
person Adarsh Mohanty    schedule 23.08.2020    source источник
comment
Это одинаково в обоих случаях, потому что вы по-прежнему посещаете каждый элемент массива только один раз.   -  person Dai    schedule 23.08.2020
comment
@Dai Разве временная сложность не должна быть меньше в 2 раза? Сложность пространства будет такой же, но теоретически 2-й метод должен принимать O(n/2)(не принимая во внимание округление до O(n), конечно)   -  person Alex.Kh    schedule 23.08.2020
comment
Подумайте об этом так: на самом деле это не извлечение элементов, которое чего-либо стоит, а то, что вы делаете с элементами массива, имеет стоимость. Эта стоимость по-прежнему должна быть оплачена один раз за каждый элемент, даже если вы вытащите два элемента, а затем будете работать с ними по отдельности.   -  person g.d.d.c    schedule 23.08.2020
comment
@Alex.Kh Обозначение Big-O (и временная сложность в целом) касается только порядка функции (скорости роста), поэтому, если у вас есть алгоритм O(1), который всегда занимает ровно 1 000 000 лет на современных процессорах, и другой алгоритм для та же проблема, которая выполняется за O(n^2) времени (но выполняется всего за несколько миллисекунд из-за некоторой оптимизации ЦП, которая делает каждую операцию очень дешевой, но все же требует выполнения n^2 раз), то это не меняет их временную сложность и миллион -year алгоритм по-прежнему менее сложен во времени.   -  person Dai    schedule 23.08.2020

Ответы (1)


arrow_upward
0
arrow_downward

Конечно же. Оба являются O (n), на самом деле нет способа пройти массив быстрее, чем O (n). Даже если вы идете в противоположном направлении, вам все равно нужно посетить каждый элемент один раз.

person haoyu wang    schedule 23.08.2020
comment
это потому, что вы мало что делали в своем цикле, поэтому время цикла стало самой трудоемкой частью. Но в реальном мире вам обычно приходится выполнять некоторую обработку для каждого элемента, в этом случае цикл while не сэкономит много времени. - person haoyu wang; 23.08.2020
comment
на самом деле нет способа пройти массив быстрее, чем O(n) — здесь я буду хитрым: если мы говорим о массивах (или векторах, или кортежах) < b>в частности тогда в случае, когда их длина n ограничена n <= hardware-units, тогда существуют O(1) алгоритмы (например, SIMD и его реализации в SSE). Я утверждаю, что это настоящие алгоритмы O(1), потому что скорость роста алгоритма равна нулю, а когда n слишком велико, алгоритм буквально не может работать. Просто говорю (на практике SIMD, используемый в алгоритмах, в конечном итоге поддерживает произвольные n, поэтому они равны O (n) - person Dai; 23.08.2020